Given a binary tree, determine if it is height-balanced.
这题是easy题。都能看出来用递归，但是怎么用递归判断每一棵subtree是不是Balanced是要点。这里是在递归中定义了int lh = helper(root.left);这样我称为「类似postorder」的递归一边递归一边判断。
方法1
- 如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了。
- 否则就利用返回的深度信息看看左右子树是不是违反平衡条件，如果违反返回-1，
- 否则返回左右子树深度大的加一作为自己的深度即可。
空间是栈高度O(logn)。
code ganker的讲解很好。
public boolean isBalanced(TreeNode root) {
return helper(root) >= 0;
}
private int helper(TreeNode root) {
if (root == null) return 0;
//这样会把所有node都当做root遍历一遍。TimeComplexity:O(n)
int lh = helper(root.left);
int rh = helper(root.right);
//这句不能落下。。。
if (lh == -1 || rh == -1) {
return -1;
}
if (Math.abs(lh - rh) >= 2) {
//技巧：返回-1代表某棵subtree imbalance 了
return -1;
}
return Math.max(helper(root.left), helper(root.right)) + 1;
}
方法2
Calling height() explicitly for each child node
看了leetcode里的discussion（这个人把方法1叫作dfs。return the height of the current node in DFS recursion。
），还可以像下面这样写，更直观，同样要注意怎么用递归判断每一棵subtree是不是Balanced是要点。这里是递归调用isBalanced()：
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int lh = height(root.left);
int rh = height(root.right);
return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int height(TreeNode root) {
if (root == null) return 0;
return Math.max(height(root.left), height(root.right)) + 1;
}
