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

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 200

题目：

方法一：

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

递归三部曲：

参数root，返回值int，若高度差还没有超过1，则返回的int是子树之间高度的最大值，若高度差大于1，则int为-1，递归终止
两个终止条件，①root==null则return 0 ②当前节点的下一层返回了-1，则return -1
单层逻辑：后序遍历，maxl maxr接住子树遍历的结果，回溯。
判断高度差是否大于1 ，是则返回-1 ，只要有一个子树出现-1即不为平衡二叉树，则终止遍历将-1传到递归顶部

class Solution {
    public boolean isBalanced(TreeNode root) {
// 基于最大深度来做
        return check(root)!=-1;
    }

    int check(TreeNode root){
        // 终止条件
        if(root==null){
            return 0;
        }

        // maxl maxr接住子树遍历的结果
        int maxl=check(root.left);
        if(maxl==-1) return -1;  // 如果有一个子树为-1即不为平衡子树则无需再比较，直接返回-1到递归顶部 

        int maxr=check(root.right);
        if(maxr==-1) return -1;

        // 后序遍历  回溯
        // 需要使用子树遍历的结果来做判断
        if(Math.abs(maxr-maxl)>1){
            return -1;
        }
        return Math.max(maxr,maxl)+1; // 若是平衡二叉树，则返回二叉树的深度
    }
}

方法二：使用flag

也可以使用flag布尔标记，一旦出现层数大于1，就令flag 为false ，最后返回flag的值即为答案；
依然基于最大深度来做；

 class Solution {
    boolean flag=true; // 布尔标记 ！
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        check(root);
        return flag;
    }

    int check(TreeNode root){
// 基于最大深度来做
        if(root==null){
            return 0;
        }
        // 后序
        int left=check(root.left);
        int right=check(root.right);
        
        if( Math.abs(left-right)>1){
            flag=false;
        }
        return Math.max(left,right)+1;
    }
}