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.

 

树的高度： Tree depth的定义：为当前节点左右subtree depth中的较大值加1.

// 判断左右子树是不是平衡，然后 左右子树的高度差不大于1

// 可以把树深度的返回 和 判断平衡树 放在一起

// 用一个特殊的返回值来代表不平衡，这样就少了一层的判断

// Tree depth的定义：为当前节点左右subtree depth中的较大值加1.

从根往上

1 class Solution { 2 public: 3     bool isBalanced(TreeNode* root) { 4         return dfs(root) == -1? false: true; 5     } 6     int dfs(TreeNode* root) 7     { 8         if (root == NULL) 9             return 0;10         int left = dfs(root -> left);11         int right = dfs(root -> right);12         if (left == -1 || right == -1|| abs(left - right) >1) return -1;13         return max(left,right) +1;14         15     }16 };

 

方法二： 

从上往下，但是会消耗跟多的时间

1 class Solution { 2 public: 3     bool isBalanced(TreeNode* root) { 4         if (root == NULL) 5             return true; 6         if (isBalanced(root->left) && isBalanced(root->right)) 7             return abs(dfs(root->left) - dfs(root->right)) >1 ? false:true;  8         return false;  9     }10     int dfs(TreeNode* root)11     {12         if (root == NULL)13             return 0;14         if (root ->left == NULL || root->right == NULL )15             return dfs(root->left) + dfs(root ->right) +1 ;16         return max(dfs(root->left),dfs(root->right))+1;17     }18 };