0099. Recover Binary Search Tree¶
题目信息¶
- 题号:
恢复二叉搜索树
- 难度:
Medium
- 主题:
二叉搜索树、中序遍历、显式栈、Morris 遍历
- 原题:
- 重点:
从中序逆序对定位两个错误节点,再用 Morris 遍历压缩辅助空间
题目重述¶
一棵原本合法的二叉搜索树中,恰好有两个不同节点的值被交换。恢复这棵树,使它重新满足二叉搜索树的严格大小关系。
只能交换节点值,不能改变任何父子连接。题目保证输入中确实存在两个被交换的节点。
树的节点数在 2..1000 范围内,节点值处于 32 位有符号整数范围内。
自建示例¶
输入(层序):[4,6,2,1,3,5,7]
中序序列:[1,6,3,4,5,2,7]
恢复后:[4,2,6,1,3,5,7]
交换值 2 和 6 后,中序序列出现 6 > 3 与 5 > 2 两次下降。第一次下降的左端是 6,最后一次下降的右端是 2。
输入(层序):[3,1,2]
中序序列:[1,3,2]
恢复后:[2,1,3]
交换的两个值在正确中序序列中相邻,因此只出现一次下降 3 > 2。
输入(层序):[2,3,1]
中序序列:[3,2,1]
恢复后:[2,1,3]
扫描到 3 > 2 时记录第一个错误节点 3,扫描到 2 > 1 时把第二个错误节点更新为 1。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
void collectInorder(TreeNode* node, std::vector<TreeNode*>& nodes) {
if (!node) return;
collectInorder(node->left, nodes);
nodes.push_back(node);
collectInorder(node->right, nodes);
}
void recordInversion(TreeNode* node, TreeNode*& previous,
TreeNode*& first, TreeNode*& second) {
if (previous && previous->val > node->val) {
if (!first) first = previous;
second = node;
}
previous = node;
}
void nodeArray(TreeNode* root) {
std::vector<TreeNode*> nodes;
collectInorder(root, nodes);
TreeNode* first = nullptr;
TreeNode* second = nullptr;
for (int index = 1; index < static_cast<int>(nodes.size()); ++index) {
if (nodes[index - 1]->val > nodes[index]->val) {
if (!first) first = nodes[index - 1];
second = nodes[index];
}
}
std::swap(first->val, second->val);
}
void explicitStack(TreeNode* root) {
std::vector<TreeNode*> stack;
TreeNode* current = root;
TreeNode* previous = nullptr;
TreeNode* first = nullptr;
TreeNode* second = nullptr;
while (current || !stack.empty()) {
while (current) {
stack.push_back(current);
current = current->left;
}
current = stack.back();
stack.pop_back();
recordInversion(current, previous, first, second);
current = current->right;
}
std::swap(first->val, second->val);
}
void morrisTraversal(TreeNode* root) {
TreeNode* current = root;
TreeNode* previous = nullptr;
TreeNode* first = nullptr;
TreeNode* second = nullptr;
while (current) {
if (!current->left) {
recordInversion(current, previous, first, second);
current = current->right;
continue;
}
TreeNode* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
recordInversion(current, previous, first, second);
current = current->right;
}
}
std::swap(first->val, second->val);
}
public:
void recoverTree(TreeNode* root) {
morrisTraversal(root);
}
};
题解¶
中序序列¶
合法二叉搜索树的中序序列严格递增。树的结构没有改变,只有两个节点值交换,因此可以把问题转化为:在一个严格递增序列中交换两个元素后,定位这两个元素并换回。
直接收集中序节点后,无需重新排序全部值。只要扫描相邻节点,找到所有满足 previous.val > current.val 的下降位置即可。
异常端点¶
设原递增序列中的较小错误值为 x,较大错误值为 y。
当二者相邻时,交换后只有一个下降:
..., y, x, ...
^ ^
first second
当二者不相邻时,交换后通常有两个下降:
..., y, ..., a, ..., b, ..., x, ...
^ ^ ^ ^
first 第一次下降 最后一次下降 second
统一记录规则如下:
遇到 previous > current:
first 只在第一次下降时取 previous
second 在每次下降时都更新为 current
一次下降时,两个端点就是相邻的错误值。两次下降时,第一次下降的左端是被提前放置的较大值,最后一次下降的右端是被推后的较小值。
数组扫描¶
最直接的方法先递归收集中序节点,再扫描相邻对。它已经把“排序所有值”的 O(n log n) 工作缩减为一次 O(n) 扫描,但仍保存了全部节点,额外空间为 O(n)。
这一步明确了真正需要保留的状态只有三个节点引用:中序前驱 previous、第一个错误节点 first 和第二个错误节点 second。
流式中序¶
显式栈能够按中序顺序逐个产生节点。当前节点一旦与 previous 比较完成,除非它成为新的前驱,否则不再需要保存;因此不必构造完整中序数组。
栈中保存的是左子树尚未访问完的祖先。每个节点入栈、出栈各一次,检测下降的逻辑与数组扫描完全相同,时间 O(n),辅助空间 O(h),其中 h 为树高。
Morris 线索¶
Morris 遍历进一步用临时线索替代显式栈。当前节点有左子树时,找到左子树最右节点 predecessor:
predecessor.right 为空:建立 predecessor.right = current,进入左子树
predecessor.right 指向 current:删除线索,访问 current,进入右子树
第一次到达当前节点时建立返回路径,第二次通过线索返回时才按中序访问它。每条临时边都会在离开左子树时恢复为 nullptr,最终树结构与输入完全一致。
节点交换¶
题目保证错误只来自两个节点值互换,所以扫描结束后只交换 first->val 与 second->val。父子连接从未改变,修复后的中序序列恢复严格递增,整棵树重新满足二叉搜索树条件。
复杂度¶
三种方法都只需一次中序扫描,时间 O(n)。节点数组方法使用 O(n) 空间,显式栈使用 O(h) 空间,Morris 方法除输出外使用 O(1) 额外空间。