Leetcode: Balanced Binary Tree-蒲公英云

Leetcode: Balanced Binary Tree

傷城~ 2022-08-07 04:35 278阅读 0赞

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题目分析：
平衡二叉树：（1）要么为空，要么左右子树的深度差值不超过1；（2）左右两个子树都是一棵平衡二叉树，即子树也都要都满足条件（1）。显然这是一个递归的定义。

C++参考示例代码：

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution
{
private:
    bool checkBalanced(TreeNode *node, int &depth)
    {
        if (node == NULL)
        {
            depth = 0;
            return true;
        }
        int leftDepth, rightDepth;
        bool leftBalanced = checkBalanced(node->left, leftDepth);
        bool rightBalanced = checkBalanced(node->right, rightDepth);
        depth = max(leftDepth, rightDepth) + 1;//求以node为根节点的深度
        return leftBalanced && rightBalanced && abs(leftDepth - rightDepth) <= 1;
    }
public:
    bool isBalanced(TreeNode *root)
    {
        int depth;
        return checkBalanced(root, depth);
    }
};