平衡⼆叉树例题_平衡⼆叉树专题
⼒扣关于平衡⼆叉树的题⽬还是有⼀些的，并且都⾮常经典，推荐⼤家练习。今天给⼤家精选了 4 道题，如果你彻底搞明⽩了这⼏道题，碰到其他的平衡⼆叉树的题⽬应该不⾄于没有思路。当你领会了我的思路之后， 建议再⼏个题⽬练⼿，巩固⼀下学习成果。
110. 平衡⼆叉树(简单)
最简单的莫过于判断⼀个树是否为平衡⼆叉树了，我们来看下。
题⽬描述
给定⼀个⼆叉树，判断它是否是⾼度平衡的⼆叉树。
本题中，⼀棵⾼度平衡⼆叉树定义为：
⼀个⼆叉树每个节点 的左右两个⼦树的⾼度差的绝对值不超过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
思路
由于平衡⼆叉树定义为就是⼀个⼆叉树每个节点的左右两个⼦树的⾼度差的绝对值不超过 1。⽤伪代码描述就是：
if abs(⾼度(root.left) - ⾼度(root.right)) <= 1 and root.left 也是平衡⼆叉树 and root.right 也是平衡⼆叉树:
print('是平衡⼆叉树')
else:
因此我们⾸先需要知道如何计算⼀个⼦树的⾼度。这个可以通过递归的⽅式轻松地计算出来。计算⼦树⾼度的 Python 代码如下：
def dfs(node, depth):
if not node: return 0
l = dfs(node.left, depth + 1)
r = dfs(node.right, depth + 1)
return max(l, r) + 1
代码
代码⽀持： Python3
Python3 Code:
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def dfs(node, depth):
if not node: return 0
l = dfs(node.left, depth + 1)
r = dfs(node.right, depth + 1)
return max(l, r) + 1
if not root: return True
if abs(dfs(root.left, 0) - dfs(root.right, 0)) > 1: return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
复杂度分析
时间复杂度：对于 isBalanced 来说，由于每个节点最多被访问⼀次，这部分的时间复杂度为 $O(N)$，⽽ dfs 函数 每次被调⽤的次数不超过 $log N$，因此总的时间复杂度为 $O(NlogN)$，其中 $N$ 为 树的节点总数。
空间复杂度：由于使⽤了递归，这⾥的空间复杂度的瓶颈在栈空间，因此空间复杂度为 $O(h)$，其中 $h$ 为树的⾼度。
108. 将有序数组转换为⼆叉搜索树(简单)
108 和 109 基本是⼀样的，只不过数据结构不⼀样，109 变成了链表了⽽已。由于链表操作⽐数组需要考虑更多的因素，因此 109 是中等难度。
题⽬描述
将⼀个按照升序排列的有序数组，转换为⼀棵⾼度平衡⼆叉搜索树。
本题中，⼀个⾼度平衡⼆叉树是指⼀个⼆叉树每个节点 的左右两个⼦树的⾼度差的绝对值不超过 1。
⽰例:
给定有序数组: [-10,-3,0,5,9],
⼀个可能的答案是：[0,-3,9,-10,null,5]，它可以表⽰下⾯这个⾼度平衡⼆叉搜索树：二叉树定义
对于这个问题或者 给定⼀个⼆叉搜索树，将其改为平衡(后⾯会讲) 基本思路都是⼀样的。
题⽬的要求是将有序数组转化为：
⾼度平衡的⼆叉树
⼆叉搜索树
由于平衡⼆叉树是左右两个⼦树的⾼度差的绝对值不超过 1。因此⼀种简单的⽅法是选择中点作为根节点，根节点左侧的作为左⼦树，右侧的作为右⼦树即可。原因很简单，这样分配可以保证左右⼦树的节点数⽬差不超过 1。因此⾼度差⾃然也不会超过 1 了。
上⾯的操作同时也满⾜了⼆叉搜索树，原因就是题⽬给的数组是有序的。
你也可以选择别的数作为根节点，⽽不是中点，这也可以看出答案是不唯⼀的。
代码
代码⽀持： Python3
Python3 Code:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
复杂度分析
时间复杂度：由于每个节点最多被访问⼀次，因此总的时间复杂度为 $O(N)$，其中 $N$ 为数组长度。
空间复杂度：由于使⽤了递归，这⾥的空间复杂度的瓶颈在栈空间，因此空间复杂度为 $O(h)$，其中 $h$ 为树的⾼度。同时由于是平衡⼆叉树，因此 $h$ 就是 $log N$。
109. 有序链表转换⼆叉搜索树(中等)
题⽬描述
`给定⼀个单链表，其中的元素按升序排序，将其转换为⾼度平衡的⼆叉搜索树。
本题中，⼀个⾼度平衡⼆叉树是指⼀个⼆叉树每个节点 的左右两个⼦树的⾼度差的绝对值不超过 1。
⽰例:
给定的有序链表： [-10, -3, 0, 5, 9],
⼀个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表⽰下⾯这个⾼度平衡⼆叉搜索树：
思路
和 108 思路⼀样。 不同的是数据结构的不同，因此我们需要关注的是链表和数组的操作差异。
(数组的情况)
我们再来看下链表：
(链表的情况)
到中点，只需要使⽤经典的快慢指针即可。同时为了防⽌环的出现， 我们需要斩断指向 mid 的 next 指针，因此需要记录⼀下中点前的⼀个节点，这只需要⽤⼀个变量 pre 记录即可。
代码
代码⽀持： Python3
Python3 Code:
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
pre, slow, fast = None, head, head
while fast :
fast =
pre = slow
slow =
if pre:
< = None
node = TreeNode(slow.val)
if slow == fast:
return node
node.left = self.sortedListToBST(head)
node.right = self.)
return node
复杂度分析
时间复杂度：由于每个节点最多被访问⼀次，因此总的时间复杂度为 $O(N)$，其中 $N$ 为链表长度。
空间复杂度：由于使⽤了递归，这⾥的空间复杂度的瓶颈在栈空间，因此空间复杂度为 $O(h)$，其中 $h$ 为树的⾼度。同时由于是平衡⼆叉树，因此 $h$ 就是 $log N$。
1382. 将⼆叉搜索树变平衡(中等)
题⽬描述
给你⼀棵⼆叉搜索树，请你返回⼀棵 平衡后 的⼆叉搜索树，新⽣成的树应该与原来的树有着相同的节点值。
如果⼀棵⼆叉搜索树中，每个节点的两棵⼦树⾼度差不超过 1 ，我们就称这棵⼆叉搜索树是 平衡的 。
如果有多种构造⽅法，请你返回任意⼀种。
⽰例：
输⼊：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯⼀的正确答案，[3,1,4,null,2,null,null] 也是⼀个可⾏的构造⽅案。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。