EEPW论坛

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. class Solution {  

2. public:  

3.     bool isBalanced(TreeNode*  root)  

4.     {  

5.         if (root==NULL)  

6.         {  

7.             return true;  

8.         }  

9.   

10.         int left = help(root->left);  

11.         int right = help(root->right);  

12.   

13.         if (left-right>=-1 && left-right<=1)  

14.         {  

15.             if (isBalanced(root->left) && isBalanced(root->right))  

16.             {  

17.                 return true;  

18.             }  

19.         }  

20.   

21.         return false;  

22.     }  

23.   

24.     int help(TreeNode* root)  

25.     {  

26.         if (root==NULL)  

27.         {  

28.             return 0;  

29.         }  

30.   

31.         if (root->left==NULL && root->right==NULL)  

32.         {  

33.             return 1;  

34.         }  

35.   

36.         return max(help(root->left), help(root->right)) + 1;  

37.     }  

38. };