剑指offer 79： 判断是不是平衡二叉树

链接：判断是不是平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路：
基于最大深度的做法，自底向上判断是否为平衡二叉树，使用后序遍历
使用int类型数作为标记，若左右子树的高度差>1 则返回-1
注意：一旦在某一个节点返回了-1 ，则-1不能再参与运算！ 直接return -1 终止递归！

递归三部曲：

1. 参数root，返回值int，若高度差还没有超过1，则返回的int是子树之间高度的最大值，若高度差大于1，则int为-1， 递归终止
2. 两个终止条件，①root==null则return 0 ②当前节点的下一层返回了-1，则return -1
3. 单层逻辑：后序遍历，判断高度差是否大于1 ，是则返回-1 ，这个-1返回给上一层递归，就会提前终止递归。

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 自底向上，后序遍历
        // 基于最大深度来做
        return check(root)!=-1;
        
    }
    int check(TreeNode root){
        int maxr=0,maxl=0;
        if(root==null){
            return 0; // ------- 终止条件1
        }
        maxl=check(root.left);
        if(maxl ==-1 ){return -1;}  // 一旦返回-1 ，则-1不能再参与运算！------- 终止条件2

        maxr=check(root.right);
        if(maxr ==-1 ){ return -1;} // ------- 终止条件2

        // 两树深度相差>1，则不是平衡树
        if(Math.abs(maxr-maxl)>1){
            return -1;
        }

        return Math.max(maxr,maxl)+1; // 返回当前节点的深度（高度）
    }
}