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