题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

题解一

自顶向下的解法。对每个节点首先求左右子树的深度之差，然后递归判断左右子树是否是平衡二叉树，如果左右子树深度之差小于2，并且左右子树都是平衡二叉树，则根节点也是平衡二叉树。其中求树的深度的方法和上一题的代码一模一样。

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 空树是平衡二叉树
        if (root == null)
            return true;
        
        // 平衡二叉树要满足两点条件：
        // 1. 左右子树高度差不超过1
        // 2. 左右子树都是平衡二叉树
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

题解二

题解一的解法很简洁，但是时间复杂度较高，在上层节点的时候，下层节点可能会被重复遍历，节点的高度会被计算多次。

因此可以考虑自下向上的解法，转化为求树的深度。如果子树是平衡二叉树，则返回子树的深度；否则停止遍历，这样每个节点最多只访问一次。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return GetDepth(root) != -1;
    }
    
    private int GetDepth(TreeNode node) {
        if (node == null)
            return 0;
        
        int left = GetDepth(node.left);
        if (left == -1) return -1; // 剪枝
        
        int right = GetDepth(node.right);
        if (right == -1) return -1; // 剪枝
        
        return Math.abs(left-right)>1 ? -1 : Math.max(left, right)+1;
    }
}