题目描述：
给出二叉搜索树的根节点root，该树中恰好有两个节点的值被错误地交换。请在不改变树结构的情况下，恢复这棵树。
数据范围：
$2\le n \le 1000;-2^{31}\le val \le 2^{31}$
题解：
中序遍历按顺序可以得到逆序对。因为两个点的值被交换，可以得到两处大于的地方，如果两个点是挨着的，那么只会有一对。遇到第二对时需要更新后面的那个错误节点。
Morris遍历：一种可以在 $O(n)$ 空间复杂度中序遍历二叉树的方法，主要是使用空右儿子指向递归返回的节点。
遍历流程如下（假设当前遍历到的是 $x$ ）：
- 如果 $x$ 没有左孩子，则直接访问 $x$ 的右孩子。
- 如果 $x$ 有左孩子，则找到 $x$ 的左子树上最右的节点（也就是左子树中序遍历中的最后一个节点， $x$ 在中序遍历中的前驱节点，记为 $pred$ ）。
- 如果 $pred$ 的右孩子为空，直接把这个空间利用起来，让它指向 $x$ ，然后访问 $x$ 的左孩子。
- 如果 $pred$ 的右孩子不为空，说明此时它的右孩子指向 $x$ ，说明已经遍历完 $x$ 的左子树了（即
dfs(x->left)完毕），将 $pred$ 的右孩子置为空，然后访问 $x$ 的右孩子。
- 重复上述操作。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<TreeNode *> a;
TreeNode *pre = nullptr;
void dfs(TreeNode *root)
{
if (root == nullptr)
return;
dfs(root->left, a.size());
if (pre && (pre->val > root->val))
{
if (a.size() == 0)
{
a.emplace_back(pre);
a.emplace_back(root);
}
else
a[1] = root;
}
pre = root;
dfs(root->right);
}
void recoverTree(TreeNode *root)
{
dfs(root);
swap(a[0]->val, a[1]->val);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
void recoverTree(TreeNode *root)
{
TreeNode *pred = nullptr, *pre = nullptr, *x = nullptr, *y = nullptr;
while (root != nullptr)
{
if (root->left)
{
pred = root->left;
while (pred->right != nullptr && pred->right != root)
pred = pred->right;
if (pred->right == nullptr)
{
pred->right = root;
root = root->left;
}
else
{
if (pre && pre->val > root->val)
{
if (x == nullptr)
x = pre;
y = root;
}
pre = root;
pred->right = nullptr;
root = root->right;
}
}
else
{
if (pre && pre->val > root->val)
{
if (x == nullptr)
x = pre;
y = root;
}
pre = root;
root = root->right;
}
}
swap(x->val, y->val);
}
};
|