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 everynode never differ by more than 1.
http://blog.csdn.net/linhuanmars/article/details/23731355要判断树是否平衡，根据题目的定义，深度是比需的信息，所以我们必须维护深度，另一方面我们又要返回是否为平衡树，那么对于左右子树深度差的判断也是必要的。这里我们用一个整数来做返回值，而0或者正数用来表示树的深度，而-1则用来比较此树已经不平衡了，如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了，否则就利用返回的深度信息看看左右子树是不是违反平衡条件，如果违反返回-1，否则返回左右子树深度大的加一作为自己的深度即可。算法的时间是一次树的遍历O(n)，空间是栈高度O(logn)。
只要在遍历时取得左右子树的深度，对比是否相差超过1就可以得出结果，需要考虑的技巧是怎么在发现不平衡之后，最迅速的返回结果，不做多余的计算。
public boolean isBalanced(TreeNode root)
{
return helper(root)>=0;
}
private int helper(TreeNode root)
{
if(root == null)
return 0;
int left = helper(root.left);
int right = helper(root.right);
if(left<0 || right<0)
return -1;
if(Math.abs(left-right)>=2)
return -1;
return Math.max(left,right)+1;
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-balanced-binary-tree.html
代码中ln 11之所以不和ln 14合并放在ln 13之后，是因为当左子树不平衡时，没有必要再对右子树求depth，直接返回-1即可。这类代码中的剪枝优化需要经常注意。
int findDepth(TreeNode *root) { if(!root) return 0; int leftDepth = findDepth(root->left); // left subtree depth if(leftDepth==-1) return -1; // exit early int rightDepth = findDepth(root->right); // right subtree depth if(rightDepth==-1) return -1; if(abs(leftDepth-rightDepth)>1) return -1; return max(leftDepth,rightDepth)+1; }http://codesays.com/2014/solution-to-balanced-binary-tree-by-leetcode/
def isBalancedHelper(self, current):
if current == None:
return (True, 0)
else:
# Check its left subtree
left = self.isBalancedHelper(current.left)
if left[0] == False:
return (False, -1)
# Check its right subtree
right = self.isBalancedHelper(current.right)
if right[0] == False:
return (False, -1)
# Check whether the depth of the two subtrees differ by
# more than 1.
if abs(left[1] - right[1]) <= 1:
height = max(left[1], right[1]) + 1
return (True, height)
else:
return (False, -1)
# @param root, a tree node
# @return a boolean
def isBalanced(self, root):
return self.isBalancedHelper(root)[0]
http://www.cnblogs.com/yuzhangcmu/p/4172667.html Using codesays to optimize2 public boolean isBalanced1(TreeNode root) { 3 return dfs(root).isBalanced; 4 } 6 // bug 1: inner class is like: "public class ReturnType {", no () 7 public class ReturnType { 8 boolean isBalanced; 9 int depth; 15 } 17 public ReturnType dfs(TreeNode root) { 20 if (root == null) { 21 return new ReturnType(0, true); 22 } 23 ReturnType ret = new ReturnType(); 24 ReturnType left = dfs(root.left); 25 ReturnType right = dfs(root.right); 27 ret.isBalanced = left.isBalanced 28 && right.isBalanced 29 && Math.abs(left.depth - right.depth) <= 1; 32 ret.depth = Math.max(left.depth, right.depth) + 1; 34 return ret; 35 }
int maxDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+max(maxDepth(root->left),maxDepth(root->right)); } bool testNode(TreeNode * root){ if (root==NULL) {return true;} if (abs(maxDepth(root->left) - maxDepth(root->right)) >1) {return false;} return (testNode(root->left) && testNode(root->right)); } bool isBalanced(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function return testNode(root); } int maxDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+max(maxDepth(root->left),maxDepth(root->right)); } int minDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+min(minDepth(root->left),minDepth(root->right)); } bool isBalanced(TreeNode *root) { int maxd = maxDepth(root); int mind = minDepth(root); if (abs(maxd-mind)<=1) {return true;} else {return false;} }http://blog.csdn.net/fightforyourdream/article/details/18693131
Not efficient:
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
// 如果子树高度差大于1，则不平衡
if(Math.abs(depth(root.left)-depth(root.right)) > 1){
return false;
}
// 递归检查左子树和右子树的平衡性
return isBalanced(root.left) && isBalanced(root.right);
}
// 帮助方法，返回树的高度
private int depth(TreeNode root){
if(root == null){
return 0;
}
return 1 + Math.max(depth(root.left), depth(root.right));
}
Read full article from Yu's Coding Garden : leetcode Question 7: Balanced Binary Tree
