leetCode 110. Balanced Binary Tree 平衡二叉树-白红宇

110. Balanced Binary Tree

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.

题目大意：

判断一颗二叉树是否为平衡二叉树。

思路：

做一个辅助函数来求的树的高度。

通过辅助函数来递归求解。

代码如下：

                         
/**
 
* Definition for a binary tree node.
 
* struct TreeNode { 
 
*     int val;
 
*     TreeNode *left;
 
*     TreeNode *right;
 
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 
* };
 
*/
class
Solution { 
public
:
    
int
depth(TreeNode* root)
    
{ 
        
if
(!root)
            
return
0;
        
int
l = depth(root->left) ;
        
int
r = depth(root->right) ;
        
return
1 + ((l > r)?l:r);
    
}
    
bool
isBalanced(TreeNode* root) { 
        
if
(!root)
            
return
true
;
        
else
        
{ 
            
int
l = depth(root->left);
            
int
r = depth(root->right);
            
if
(l + 1 < r || r + 1 <l)
            
{ 
                
return
false
;
            
}
            
else
                
return
(isBalanced(root->left) && isBalanced(root->right) );
        
}
    
}
};
        
      

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1835477