【LeetCode】剑指 Offer 55 – II. 平衡二叉树 – Go 语言题解

导读:本篇文章讲解 【LeetCode】剑指 Offer 55 – II. 平衡二叉树 – Go 语言题解,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com


一、题目描述

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中 任意节点 的左右子树的深度相差不超过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


二、我的题解

注意,一棵树是平衡二叉树的条件是树中 任意节点 的左右子树的深度相差不超过1。

也就是说,对任意一个节点都需要判断其左右子树的深度差。

就像官方题解中所说的,这道题中的平衡二叉树的定义是:二叉树的 每个节点 的左右子树的高度差的绝对值不超过 1,则二叉树是平衡二叉树。根据定义,一棵二叉树是平衡二叉树,当且仅当其所有子树也都是平衡二叉树,因此可以使用递归的方式判断二叉树是不是平衡二叉树,递归的顺序可以是 自顶向下 或者 自底向上

1. 递归 – 自顶向下

我以下的递归法属于 自顶向下 ,如果树的每一个节点都满足以下三个条件,那么它就是平衡二叉树:

  1. 其左右子树的深度差不超过1
  2. 左子树是平衡二叉树
  3. 右子树是平衡二叉树
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil{
        return true
    }
    
    depl := maxDepth(root.Left)
    depr := maxDepth(root.Right)
    
    if (depl == depr || depl - depr == 1 || depr - depl == 1) && isBalanced(root.Left) && isBalanced(root.Right){
        return true
    }
    
    return false
}


func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }else{
        a := maxDepth(root.Left)
        b := maxDepth(root.Right)
        if a >= b{
            return 1 + a
        }else{
            return 1 + b
        }
    }
}

评判结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度:O(n2),其中 n 是二叉树中的节点个数。
  • 空间复杂度:O(n),其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过 n。

2. 递归 – 自底向上

方法一由于是自顶向下递归,因此对于同一个节点,函数 maxDepth 会被重复调用,导致时间复杂度较高。如果使用自底向上的做法,则对于每个节点,函数 maxDepth 只会被调用一次。

以下代码实现自底向上递归,下面的函数 high 不仅实现了 maxDepth 函数能返回树深度的功能,还兼职判断当前节点所在的子树是否平衡(判断其左右子树的深度差有没有超过 1 )。如果超过 1,返回非深度值 -1。

自底向上递归的做法类似于后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 −1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

所以如果 a := high(root.Left)b := high(root.Right) 出现 -1 值,函数 high 将一直返回 -1,直到根节点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil{
        return true
    }
    return high(root) > -1
   
}
 //如果 root 的左右子树相差在 1 之内,返回 root 高度 ; 否则返回 -1
func high(root *TreeNode) int {
    if root == nil{
        return 0
    }else{
        a := high(root.Left)
        b := high(root.Right)
        if a > -1 && b > -1 {
            if a - b > 1 || b - a > 1{
                return -1
            }else if a == b || a - b == 1{
                return 1 + a
            }else if b - a == 1{
                return 1 + b
            }
        }else{
            return -1
        }
    }
    return 0
}

评判结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度:O(n),其中 n 是二叉树中的节点个数。使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是 O(n)。

  • 空间复杂度:O(n),其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过 n。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/118963.html

(0)
seven_的头像seven_bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!