Balance Tree

出处

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.

Solution

回顾二叉树是否平衡的定义：一颗二叉树是平衡的，当且仅当左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。同时，注意特例，空树是一棵平衡二叉树。子树平衡是全局问题的一部分，因此可以通过子问题的结果来推断全局的结果：判断高度差的绝对值不超过1，以及递归左右子树都为平衡二叉树。

计算高度的子函数我们也可以用递归来实现。首先，考虑递归的出口：当node为空的时候，高度应该为0。其次，如果node不为空，那么这棵树的高度应该为左右子树中的高度较高者加1。

Complexity

对于这个实现，isBalanced函数对于每个节点只运行一次。然而，level函数会进行很多重复的计算：每次进入isBalanced函数，调用level会遍历一遍所有子节点。原因在于level函数没有记忆性，当输入为同一个节点时，level函数会再次进行完整的计算。

一种改进方式是，可以考虑利用动态编程的思想，将TreeNode指针作为键，高度作为值，一旦发现节点已经被计算过，直接返回结果，这样，level函数对每个节点只计算一次。另一种更为巧妙的方法是，isBalanced返回当前节点的高度，用-1表示树不平衡。 将计算结果自底向上地传递，并且确保每个节点只被计算一次，复杂度O(n)。

Code

有重复计算的方法

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

boolean isBalanced(Node root){
    if (root == null) return true;
    int delta = abs(level(root.left) - level(root.right));
    return delta < 2 && isBalanced(root.left) && isBalaned(root.right);
}

无重复计算的方法，返回当前节点的高度

int curHeight(Node root){
    if (root == null) 
        return 0;
        
    int left = curHeight(root.left);
    if (left == -1){
        return -1;
    }
    
    int right = curHeight(root.right);
    if (right == -1){
        return -1;
    }
    
    if (abs(left - right) > 1){
        return -1;
    }
    
    return Math.max(left, right) + 1;
}

bool isBalance(Node root){
    if (curHeight(root) == -1){
        return false;
    }
    return true;
}