110. Balanced Binary Tree

Leetcode Tree Depth-first Search

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.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7
Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Return false.

分析

在遍历树的每个结点的时候，调⽤函数height()得到它的左右⼦树的深度。如果每个结点的左右⼦树的深度相差都不超过1，按照定义 它就是⼀棵平衡的⼆叉树。

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    if (Math.abs(height(root.left, 1) - height(root.right, 1)) > 1) 
        return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

求二叉树高度的方法heightOfTree有两种方案。第一种是自顶向下计数的方法。还有一种是自底向上计数的方法。

// 自顶向下
private int height(TreeNode root, int height) {
    if (root == null) return height;
    return  Math.max(height(root.left, height + 1),
            height(root.right, height + 1));
}
// 自底向上
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) {
    return height(root) != -1;
}

private int height(TreeNode root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    if (leftHeight == -1) return -1;
    int rightHeight = height(root.right);
    if (rightHeight == -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    return Math.max(leftHeight, rightHeight) + 1;

由于只遍历了一遍二叉树，所以时间复杂度是$O(n)$. 从顶向下计数的方法在最坏情况下的复杂度是$O(n^2)$.