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

• 一、题目描述
• 二、我的题解
• • 1. 递归 - 自顶向下
  • 2. 递归 - 自底向上

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

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(n²)，其中 n 是二叉树中的节点个数。
• 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

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

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

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

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

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。