LeetCode 题解工作台
恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。 请在不改变其结构的情况下，恢复这棵树 。 示例 1： 输入： root = [1,3,null,null,2] 输出： [3,1,null,null,2] 解释： 3 不能是 1 的左孩子，因为 3 > 1 。交换 1 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
中序遍历二叉搜索树，得到的序列是递增的。如果有两个节点的值被错误地交换，那么中序遍历得到的序列中，一定会出现两个逆序对。我们用 `first` 和 `second` 分别记录这两个逆序对中较小值和较大值的节点，最后交换这两个节点的值即可。 时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例 1：
输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
- 树上节点的数目在范围
[2, 1000]内 -231 <= Node.val <= 231 - 1
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
解题思路
方法一：中序遍历
中序遍历二叉搜索树，得到的序列是递增的。如果有两个节点的值被错误地交换，那么中序遍历得到的序列中，一定会出现两个逆序对。我们用 first 和 second 分别记录这两个逆序对中较小值和较大值的节点，最后交换这两个节点的值即可。
时间复杂度 ，空间复杂度 。其中 是二叉搜索树的节点个数。
# 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 recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def dfs(root):
if root is None:
return
nonlocal prev, first, second
dfs(root.left)
if prev and prev.val > root.val:
if first is None:
first = prev
second = root
prev = root
dfs(root.right)
prev = first = second = None
dfs(root)
first.val, second.val = second.val, first.val
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you identify the two swapped nodes in a single traversal?
- question_mark
Can you restore the BST without creating new nodes or changing its structure?
- question_mark
Will you handle edge cases where swapped nodes are adjacent in in-order sequence?
常见陷阱
外企场景- error
Failing to track the previous node correctly, causing missed inversion points.
- error
Swapping incorrect nodes when the swapped nodes are not adjacent, producing an invalid BST.
- error
Using extra storage like a full array of node values instead of pointers, increasing space unnecessarily.
进阶变体
外企场景- arrow_right_alt
Recover BST when multiple pairs of nodes are swapped.
- arrow_right_alt
Recover BST using Morris Traversal to achieve O(1) space.
- arrow_right_alt
Recover a BST where only leaf nodes may be swapped, requiring subtree checks.