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

思路:

• 1、根据题意，左右子树高度差不能超过1，即Math.abs(leftHigh-rightHigh) <= 1;
• 2、计算出二叉树左右子树的高度，再计算高度差，即可判断是不是平衡的二叉树；
• 3、再分别判断左右子树是不是平衡的；

代码实现：

public static boolean isBalanceTree(TreeNode root) {
        if (root == null)
            return true;
        int diff = traverse(root.left) - traverse(root.right);
        return (Math.abs(diff) <= 1) && isBalanceTree(root.left) && isBalanceTree(root.right);
    }

    /**
     * 后续遍历计算二叉树的高度
     * 
     * @param root
     * @return
     */
    private static int traverse(TreeNode root) {
        if (root == null)
            return 0;
        int left = traverse(root.left);
        int right = traverse(root.right);
        return Math.max(left, right) + 1;
    }