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.

 

code : 

 

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    bool isBalanced(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(root == NULL)  
            return true;  
        int ld = treedepth(root->left);  
        int rd = treedepth(root->right);  
        if(abs(ld - rd) > 1)  
            return false;  
        return isBalanced(root->left) && isBalanced(root->right);  
    }  
      
    int treedepth(TreeNode *root)  
    {  
        if(root == NULL)   
            return 0;  
        int ldepth = treedepth(root->left);  
        int rdepth = treedepth(root->right);  
        return ldepth > rdepth ? ldepth+1:rdepth+1;   
    }  
};  

 

 

上面算法效率低，因为重复访问了结点，优化下，改成后序遍历即可。

 

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    bool isBalanced(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        int depth = 0;  
        return isbalance(root, depth);  
          
    }  
    bool isbalance(TreeNode *root, int &depth)  
    {  
        if(root == NULL)  
        {  
            depth = 0;  
            return true;  
        }  
        int ld,rd;  
        if( isbalance(root->left,ld) && isbalance(root->right,rd))  
        {  
            if( abs(ld - rd) > 1)  
            {  
                return false;  
            }  
            depth = ld > rd ? ld + 1 : rd + 1;  
            return true;  
        }  
    }  
      
      
};  

 

 

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