题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

https://leetcode-cn.com/problems/balanced-binary-tree/

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3    
   / \   
  9  20     
    /  \    
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

           1
          / \
         2   2
        / \ 
       3   3
      / \ 
     4   4

返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – Top-down

我们就按照定义来，求得节点左右子树的高度（在实现时用的深度），如果相差不超过1，这个子树就是平衡二叉树。我们递归地对每一个节点都进行这样的判断，直到最后轮到判断跟节点。如果跟节点也满足这样的定义，那么这棵树就是平衡二叉树。

对于求得一个顶点的深度的算法，时间复杂度为O(n)。但是二叉树有n个节点，总体时间复杂度为O(n^2)。如果树是链式结构，那么空间复杂度最高，为O(n)。全部代码如下：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;

        int lDepth = getDepth(root.left, 1);
        int rDepth = getDepth(root.right, 1);

        if (Math.abs(lDepth - rDepth) > 1)
            return false;

        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int getDepth(TreeNode node, int depth) {
        if (node == null)
            return 0;

        return Math.max(getDepth(node.left, depth),
                getDepth(node.right, depth)) + 1;
    }
}

解法2 – Bottom-up

Bottom-up算法自下而上地求得每个顶点的高度，根据左右子树的高度差判断是否平衡。如果某个顶点的左右子树的高度之差已经超过1了，那么我们也不必要继续向上判断了。这样，我们发现有任何一颗子树是不平衡的，我们就可以提前终止算法。就算了所有的子树都是平衡点，所有顶点也只扫描一次。

因此Bottom-up算法的时间复杂度O(n)，空间复杂度O(n)。全部代码如下：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null)
            return 0;

        int lHeight = getHeight(node.left);
        if (lHeight == -1)
            return -1;

        int rHeight = getHeight(node.right);
        if (rHeight == -1)
            return -1;

        // Bottom-up，发现不平衡提前退出
        if (Math.abs(lHeight - rHeight) > 1)
            return -1;

        return Math.max(lHeight, rHeight) + 1;
    }
}