算法1

(递归)

在上一题的基础上，得出左右子树的深度，然后求差，如果大于1，则返回false;

然后递归每个节点，这个算法的弊端是，每个节点递归两次

Java 代码

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

        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        int diff = left-right;
        if(Math.abs(diff)>1)
            return false;

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

    public int treeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }

        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        return left>right?left+1:right+1;
    }
}

算法2

(后序遍历) $O(n)$

后续遍历，得到的左右子树的高度差立即进行判断即可

Java 代码

class Solution {
    private boolean isBalanced=true;
    public boolean isBalanced(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }

    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);

        if(Math.abs(left-right)>1){
            isBalanced=false;
        }
        return right>left ?right+1:left+1;

    }
}