LeetCode 题解工作台
将二叉搜索树变平衡
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。 示例 1： 输入： root = [1,null,2,null,…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
由于原树是一棵二叉搜索树，因此我们可以将其中序遍历的结果保存在一个数组 中，然后我们设计一个函数 $build(i, j)$，它用来构造 中下标范围 $[i, j]$ 内的平衡二叉搜索树，那么答案就是 $build(0, |nums| - 1)$。 函数 $build(i, j)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
示例 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] 也是一个可行的构造方案。
示例 2：
输入: root = [2,1,3] 输出: [2,1,3]
提示：
- 树节点的数目在
[1, 104]范围内。 1 <= Node.val <= 105
解题思路
方法一：中序遍历 + 构造平衡二叉树
由于原树是一棵二叉搜索树，因此我们可以将其中序遍历的结果保存在一个数组 中，然后我们设计一个函数 ，它用来构造 中下标范围 内的平衡二叉搜索树，那么答案就是 。
函数 的执行逻辑如下：
- 如果 ，那么平衡二叉搜索树为空，返回空节点；
- 否则，我们取 作为根节点，然后递归构建左子树和右子树，返回根节点。
时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
def dfs(root: TreeNode):
if root is None:
return
dfs(root.left)
nums.append(root.val)
dfs(root.right)
def build(i: int, j: int) -> TreeNode:
if i > j:
return None
mid = (i + j) >> 1
left = build(i, mid - 1)
right = build(mid + 1, j)
return TreeNode(nums[mid], left, right)
nums = []
dfs(root)
return build(0, len(nums) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate understanding of binary search tree properties.
- question_mark
Look for an efficient use of recursion in constructing the tree.
- question_mark
Pay attention to the explanation of how to balance the tree using the middle element.
常见陷阱
外企场景- error
Not using in-order traversal to get the sorted node values.
- error
Incorrectly choosing the root node (must be the middle of the sorted list).
- error
Failing to handle large trees efficiently, leading to stack overflows or memory issues.
进阶变体
外企场景- arrow_right_alt
How would this approach change if the input was a linked list?
- arrow_right_alt
What if the tree is already balanced? Can we optimize the process?
- arrow_right_alt
What if we need to maintain the original structure of the tree instead of balancing it?