题解 | #判断是不是平衡二叉树#

平衡二叉树的定义：左右子树高度差的绝对值 <= 1，且左右子树都是平衡二叉树

显然，具有递归特性，考虑使用递归。

此时，需要计算左右子树的高度差，以及左右子树各自是否是平衡二叉树，显然一个是int，一个是boolean

需要确定递归过程或者说递归返回值，是递归深度int，还是递归是否是平衡二叉树boolean，由于是否是平衡二叉树是结果，判断过程依赖于深度，且递归boolean不便于确定递归终止条件，所以主要递归深度。

考虑将深度int转化为是否为平衡二叉树的boolean，可以 设非平衡二叉树的深度返回值为-1，平衡二叉树返回非-1的具体深度值

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {

        if (root == null) {
            return true;
        }
        return depthDiff(root) == -1 ? false : true;
    }

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

        int left = depthDiff(root.left);
        int right = depthDiff(root.right);
        // 如果有一方等于-1，直接返回-1，因为左右子树已经有一方不是平衡二叉树了
        if (left == -1 || right == -1) {
            return -1;
        }
        // > 1，说明已经不是平衡二叉树了
        if (Math.abs(left - right) > 1) {
            return -1;
        } else {
            // 如果是平衡二叉树，返回较大深度
            return Math.max(left, right) + 1;
        }
    }
}