每日算法：平衡二叉树-清一色财经

每日算法：平衡二叉树

清一色 • 2023年5月5日 18:25 • 技术开发 • 阅读 13703

自顶向下的比较每个节点的左右子树的最大高度差，如果二叉树中每个节点的左右子树最大高度差小于等于 1 ，即每个子树都平衡时，此时二叉树才是平衡二叉树.

[[426529]]

本文转载自微信公众号「三分钟学前端」，作者sisterAn 。转载本文请联系三分钟学前端公众号。

关于树基础看这里：适合初学者的树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

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

3
/\
920
/\
157

返回 true 。

示例 2:

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

1
/\
22
/\
33
/\
44

返回 false 。

解答一：自顶向下(暴力法)

解题思路：自顶向下的比较每个节点的左右子树的最大高度差，如果二叉树中每个节点的左右子树最大高度差小于等于 1 ，即每个子树都平衡时，此时二叉树才是平衡二叉树

代码实现：

constisBalanced=function(root){
if(!root)returntrue
returnMath.abs(depth(root.left)-depth(root.right))<=1
&&isBalanced(root.left)
&&isBalanced(root.right)
}
constdepth=function(node){
if(!node)return-1
return1+Math.max(depth(node.left),depth(node.right))
}

复杂度分析：

时间复杂度：O(nlogn)，计算 depth 存在大量冗余操作
空间复杂度：O(n)

解答二：自底向上(优化)

解题思路：利用后续遍历二叉树(左右根)，从底至顶返回子树最大高度，判定每个子树是不是平衡树，如果平衡，则使用它们的高度判断父节点是否平衡，并计算父节点的高度，如果不平衡，返回 -1 。

遍历比较二叉树每个节点的左右子树深度：

比较左右子树的深度，若差值大于 1 则返回一个标记 -1 ，表示当前子树不平衡
左右子树有一个不是平衡的，或左右子树差值大于 1 ，则二叉树不平衡
若左右子树平衡，返回当前树的深度(左右子树的深度最大值 +1 )

代码实现：

constisBalanced=function(root){
returnbalanced(root)!==-1
};
constbalanced=function(node){
if(!node)return0
constleft=balanced(node.left)
constright=balanced(node.right)
if(left===-1||right===-1||Math.abs(left-right)>1){
return-1
}
returnMath.max(left,right)+1
}

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

©本文为清一色官方代发，观点仅代表作者本人，与清一色无关。清一色对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。本文不作为投资理财建议，请读者仅作参考，并请自行承担全部责任。文中部分文字/图片/视频/音频等来源于网络，如侵犯到著作权人的权利，请与我们联系（微信/QQ:1074760229）。转载请注明出处：清一色财经