星星博客 »  > 

2021-06-02平衡树

力扣
**平衡树的定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1 **

解题思路

首先,定义一个求二叉树高度的函数Height(),然后递归判断

class Solution {
public:
    //求二叉树高度
    int Height(TreeNode* root)
    {
        if(root == nullptr) return 0;
        return max(Height(root->left),Height(root->right))+1;
    }
    
    bool isBalanced(TreeNode* root)
    {
        if(root == nullptr) return true;
        return abs(Height(root->left)-Height(root->right)) == 1 && isBalanced(root->right) && isBalanced(root->left);
    }
};

相关文章