闯关leetcode——110. Balanced Binary Tree

大纲

题目
- 地址
- 内容
解题
- 代码地址

题目

地址

https://leetcode.com/problems/balanced-binary-tree/description/

内容

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:
在这里插入图片描述

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

解题

这题就是要检验一棵树是否是平衡二叉树。

平衡二叉搜索树（英语：Balanced Binary Search Tree）是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过1的二叉树。它能在O(log_n})内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。

这题的解法就是实现：检验所有节点的左右子树高度差。
树的高度可以通过下面算法获得，即左右子树中最高高度+1为本节点高度。

    int height(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(height(root->left), height(root->right));
    }

然后递归检测每个节点是否符合左右两子树高度差都不超过1的特点。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
private:
    int height(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(height(root->left), height(root->right));
    }
};