剑指 Offer 55 - II. 平衡二叉树

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false

限制:

  • 0 <= 树的结点个数 <= 10000

一、先序遍历 + 判断深度 (从顶至底)

这个做题的思路与剑指 Offer 55 - I. 二叉树的深度 _
类似,可以借鉴他的模板得出二叉树的深度。然后求出左节点与右节点的深度以后,看是否小于等于1,小于true,否则false。

private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

代码如下:

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        } else {
            return false;
        }
        
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left + 1, right + 1);
    }
}

这是K神的思路,把代码更简洁了。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

二、后序遍历 + 剪枝 (从底至顶)

这个是k神针对此题最优解法,确实一般人想不到,k神yyds。

这个是注释版本:

public class Solution55_2 {

    public boolean isBalanced(TreeNode root) {
        return dfs(root)==-1?false:true;
    }

    //用left,right记录root左右子节点的深度,避免遍历root时对左右节点的深度进行重复计算。
    //考虑到需要同时记录各个节点的深度和其是否符合平衡性要求,这里的返回值设为int,用一个特殊值-1来表示出现不平衡的节点的情况,而不是一般采用的boolean
    public int dfs(TreeNode root){
    	//用后序遍历的方式遍历二叉树的每个节点(从底至顶),先左子树,再右子树,最后根节点,
        if(root==null) return 0;//root等于0时,该节点符合要求,返回其深度0,而不返回-1;
        int left = dfs(root.left);//left最开始的取值为0,从底朝上遍历,先左子树,后右子树,最后根节点
        if(left==-1) return -1;//若出现节点的深度为-1,则进行剪枝,开始向上返回,之后的迭代不再进行
        int right = dfs(root.right);
        if(right==-1) return -1;
        return Math.abs(right-left)<2?Math.max(left,right)+1:-1;//+1不能少
        //最开始计算的是左子树最左侧的一个叶节点,其左右子节点不存在,left=0,right=0,满足条件,返回该叶节点的深度max(0,0)+1=1;
    }
}

这个是K神的算法流程:
recur(root) 函数

  • 返回值:
    1.当节点root 左 / 右子树的深度差 ≤1 :则返回当前子树的深度,即节点 root 的左 / 右子树的深度最大值 +1 ( max(left, right) + 1 );

    2.当节点root 左 / 右子树的深度差 > 2:则返回 -1 ,代表 此子树不是平衡树 。

  • 终止条件:
    1.当 root 为空:说明越过叶节点,因此返回高度 0 ;
    2.当左(右)子树深度为 -1:代表此树的 左(右)子树 不是平衡树,因此剪枝,直接返回 −1 ;
    isBalanced(root) 函数:

返回值:

  • 若 recur(root) != -1 ,则说明此树平衡,返回 truetrue ; 否则返回 falsefalse 。

    代码如下:

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

参考链接:

https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/

上一篇:10组-Alpha冲刺-2/6


下一篇:算法图解: 1.二分查找