[LeetCode] Balanced Binary Tree

 

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，那么它就不是高度平衡的二叉树。

 

 

class Solution {  
public:  
    int height(TreeNode *root)  
    {  
        if(root == NULL)  
            return 0;  
  
        int lh = height(root->left);  
        int rh = height(root->right);  
        return lh>rh ? lh+1 : rh+1;  
    }  
  
    bool isBalanced(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(root == NULL)  
            return true;  
        if(!isBalanced(root->left) ||  
           !isBalanced(root->right) ||  
           height(root->left) - height(root->right) > 1 ||  
           height(root->right) - height(root->left) >1)  
            return false;  
        else  
            return true;  
    }  
};  

 

补充：软件开发 , C++ ,