BM36. [判断是不是平衡二叉树]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM36. 判断是不是平衡二叉树

题目分析

这个题目就更容易了，什么叫平衡二叉树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这不就是一个双子树问题吗？另外求子树高度也是一个后序遍历问题。这不是一个双子树问题嵌套后序遍历。

具体做法

双子树的模板都是

public xxx  handler(TreeNode root){
  xxx isA = handler(root.left) 
  xxx isB = handler(root.right);
  return isA && isB;
}

二叉树的最大深度

 private int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int l= maxDepth(root.left);
        int r=maxDepth(root.right);
        // 后序遍历来了
        int max = Math.max(l, r) + 1;
      return max;
    }

套用这两个模板直接解题

public boolean IsBalanced_Solution(TreeNode root) {
      if(root == null)
          return true;
      int l = maxDepth(root.left);
      int r = maxDepth(root.right);
      //先拿到两个高度 拿到退出条件
      if(Math.abs(l - r) > 1)
          return false;
       boolean isA = IsBalanced_Solution(root.left) 
       boolean isB = IsBalanced_Solution(root.right);
       return isA && isB;
    }

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

复杂度分析：

• 时间复杂度：，其中为树的节点数，两个递归最深都为
• 空间复杂度：，递归栈最大深度

tpId=295&sfm=github&channel=nowcoder