Balanced Binary Tree

• Easy
• keyword: Recursion, Top-down, Bottom-up
• 类似: LCA, Tree diameter, Closest BST value

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.
• 这道题目加深了对于Top-down, Bottom-up的理解, 以及复杂度的分析. 好题.

想法

• 既然是比较每一个subtree的高度, 自然要用到求高度的helper function. 就是之前做的max height of Tree, 我认为BBT的性质就是max height-min height <= 1. 所以再求一个min height of tree即可. 但事实上, 这样做是不对的. 请看1337c0d3r的解释, 如下图所示, 这是一个 BBT. 显然max是5, min是3. 不能用$$max-min\le1$$来检验.

        ____1____
       /         \
      2           2
     /  \        / \
    3    3      3   3
   /\    /\    /\
  4  4  4  4  4  4 
 /\
5  5

• 所以还是必须要每一个都检查一遍.

idea 1: top-down

• 很显然, 还是使用max height of tree这个helper function, 但是是对每一个左右子树进行判断. 若该层的subtrees满足条件, 那么就向下走到下一层来.
• 所以复杂度是: 对于每一个root的左右儿子进行maxHeight (这个是O(N)的复杂度), 然后对每一个root的左右kid进行recursion call(这个是O(2N)的复杂度). 所以是$$O(N) * O(2N) = O(2N^2)$$.)
• 代码如下:

private int height(TreeNode root) {
    if (root == null)  return 0;
    return Math.max(height(root.left), height(root.right))+1;
}

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);
}

idea 2: Bottom-up : 参考The bottom up O(N) solution would be better

• 看了discuss, 发现原来: Bottom-up不仅仅是反向思维, 更是复杂度也不同了!
• 这里计算当前node的左右子树的高度, 若有一支返回-1, 表明该支in-balanced. 于是直接pass to parent, 然后一级级walk-up the tree.
• 所以是从bottom开始向上, 于是每一个node只要access一次, 所以是O(N)的复杂度!
• 所以只要对root求dfsHeight即可.
• 代码如下:

private int dfsHeight(TreeNode root) {
    if (root == null)  return 0;
    int lh = dfsHeight(root.left);
    if (lh == -1)  return -1;
    int rh = dfsHeight(root.right);
    if (rh == -1)  return -1;
    if (Math.abs(lh-rh) > 1)  return -1;
    return Math.max(lh,rh)+1;
}

public boolean isBalanced(TreeNode root) {
    return dfsHeight(root) != -1?
}