110.平衡二叉树 (Easy)*

题目描述*

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例*

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

代码*

最简单的就是用之前写过的递归求深度，计算比较左右子树深度。但是无疑会出现重复计算高度的问题，我们可以在计算高度的时候就判断是否平衡。

递归求深度optimized

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

class Solution {
public:
    int getDepth(TreeNode *root) {
        if(root == nullptr) {
            return 0;
        }
        int lDepth = getDepth(root->left);
        if(lDepth == -1) {
            return -1;
        }
        int rDepth = getDepth(root->right);
        if(rDepth == -1) {
            return -1;
        }
        if(abs(lDepth - rDepth) > 1) {
            return -1;
        }
        return max(lDepth, rDepth) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) {
            return true;
        }
        return getDepth(root) != -1;
    }
};

最后更新: July 23, 2022