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.

分析：判断一颗二叉树是否是平衡的，dfs递归求解，递归的过程中顺便求得树的高度                                      

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  * int val; 5  * TreeNode *left; 6  * TreeNode *right; 7  * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isBalanced(TreeNode *root) {13         // IMPORTANT: Please reset any member data you declared, as14         // the same Solution instance will be reused for each test case.15         if(root == NULL)return true;16         if(height(root) == -1)return false;17         else return true;18     }19     //若root是平衡树，那么返回树的高度，否则返回-120     int height(TreeNode *root)21     {22         if(root->left == NULL && root->right == NULL)return 1;23         int leftHeight = 0, rightHeight = 0;24         if(root->left)25             leftHeight = height(root->left);26         if(leftHeight == -1)return -1;27         if(root->right)28             rightHeight = height(root->right);29         if(rightHeight == -1)return -1;30         if(abs(leftHeight-rightHeight) > 1)return -1;31         return 1+max(leftHeight, rightHeight);32     }33 };

【版权声明】转载请注明出处：