0099. Recover Binary Search Tree
================================
题目信息
--------
:题号: 0099. 恢复二叉搜索树
:难度: Medium
:主题: 二叉搜索树、中序遍历、显式栈、Morris 遍历
:原题: `LeetCode 0099 `_
:重点: 从中序逆序对定位两个错误节点,再用 Morris 遍历压缩辅助空间
题目重述
--------
一棵原本合法的二叉搜索树中,恰好有两个不同节点的值被交换。恢复这棵树,使它重新满足二叉搜索树的严格大小关系。
只能交换节点值,不能改变任何父子连接。题目保证输入中确实存在两个被交换的节点。
树的节点数在 ``2..1000`` 范围内,节点值处于 32 位有符号整数范围内。
自建示例
--------
.. code-block:: text
输入(层序):[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。
.. code-block:: text
输入(层序):[3,1,2]
中序序列:[1,3,2]
恢复后:[2,1,3]
交换的两个值在正确中序序列中相邻,因此只出现一次下降 ``3 > 2``。
.. code-block:: text
输入(层序):[2,3,1]
中序序列:[3,2,1]
恢复后:[2,1,3]
扫描到 ``3 > 2`` 时记录第一个错误节点 3,扫描到 ``2 > 1`` 时把第二个错误节点更新为 1。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
void collectInorder(TreeNode* node, std::vector& 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 nodes;
collectInorder(root, nodes);
TreeNode* first = nullptr;
TreeNode* second = nullptr;
for (int index = 1; index < static_cast(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 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``。
当二者相邻时,交换后只有一个下降:
.. code-block:: text
..., y, x, ...
^ ^
first second
当二者不相邻时,交换后通常有两个下降:
.. code-block:: text
..., y, ..., a, ..., b, ..., x, ...
^ ^ ^ ^
first 第一次下降 最后一次下降 second
统一记录规则如下:
.. code-block:: text
遇到 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``:
.. code-block:: text
predecessor.right 为空:建立 predecessor.right = current,进入左子树
predecessor.right 指向 current:删除线索,访问 current,进入右子树
第一次到达当前节点时建立返回路径,第二次通过线索返回时才按中序访问它。每条临时边都会在离开左子树时恢复为 ``nullptr``,最终树结构与输入完全一致。
节点交换
~~~~~~~~
题目保证错误只来自两个节点值互换,所以扫描结束后只交换 ``first->val`` 与 ``second->val``。父子连接从未改变,修复后的中序序列恢复严格递增,整棵树重新满足二叉搜索树条件。
复杂度
~~~~~~
三种方法都只需一次中序扫描,时间 ``O(n)``。节点数组方法使用 ``O(n)`` 空间,显式栈使用 ``O(h)`` 空间,Morris 方法除输出外使用 ``O(1)`` 额外空间。