题目链接
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
显式中序遍历
这种方法，我们需要借助一个数组，保存二叉树的中序遍历(左-根-右)顺序，一颗二叉搜索树的前序遍历是有序数列(从小到大)。遍历完成后，只需遍历数组就可以找到哪两个节点被错误交换了位置。
如上图所示，左边子树的中序遍历为: 3 2 1。正常应该为递增数列，很明显 3 和 1被交换了位置，正确顺序应该为：1 2 3，只需交换 3 和 1 的节点值即可。
我们使用节点类型的数组，直接保存节点，而不是节点值，后续就可以直接交换节点值了，不然又要遍历修改。
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
| class Solution {
public:
vector<TreeNode*> vec;
void dfs(TreeNode* root){
if(root!=nullptr){
dfs(root->left);
vec.push_back(root);
dfs(root->right);
}
}
void recoverTree(TreeNode* root) {
dfs(root);
TreeNode* x;
bool isNotLast = false;
int i=0;
for(; i<vec.size()-1; ++i){
if(vec[i]->val>vec[i+1]->val){
x = vec[i];
break;
}
}
while(i+1<vec.size()){
if(vec[++i]->val>=x->val){
isNotLast = true;
break;
}
}
if(isNotLast){
i = i-1;
}
swap(x->val,vec[i]->val);
}
};
|
时间复杂度
DFS 耗时 O(n)，后续只需循环一次，最多耗时 O(n)，n 为节点个数，所以总的时间复杂度为 O(2n)=O(n)。
空间复杂度
存储遍历需要 O(n)，递归所需空间O(H*1)，H 为二叉搜索树的深度，因为 O(H*1) <= O(n)，根据渐进关系，空间复杂度为 O(n)。
隐式中序遍历
有没有办法只需一次遍历就可以找到两个被错误交换的节点。使用 pre 标记节点的前驱，如果当前节点 root->val < pre->val，说明root 和 pre 应该交换。
由上图所示，当使用中序遍历时，记录每个节点的前驱节点，初始化 pre == nullptr。
root 为 1 时，它的前驱为 nullptr，设置 pre 为 1
root 为 3 时，它的前驱为 1，root 应该大于它的前驱，设置 pre 为 3
root 为 2时，它的前驱为 3，root 应该大于它的前驱，但此时 root 小于了前驱，说明应该交换 root 和 它的前驱。到此时 DFS 的任务完成。设置 pre 为 2
root 为 4时，它的前驱为 2，root 应该大于它的前驱，设置 pre 为 4
DFS 结束，找到了应该结合的两个节点。 3 和 2。
代码如下：
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
| class Solution {
public:
TreeNode* x = nullptr;
TreeNode* y = nullptr;
TreeNode* pre = nullptr;
void dfs(TreeNode* root){
if(root==nullptr)
return;
dfs(root->left);
if(pre!=nullptr && root->val<pre->val){
y = root;
if(x==nullptr){
x = pre;
}else{
return;
}
}
pre = root;
cout<<"pre="<<pre->val<<endl;
dfs(root->right);
}
void recoverTree(TreeNode* root) {
dfs(root);
swap(x->val,y->val);
}
}
|
时间复杂度
DFS 的时间复杂度：O(n)，n 为节点个数，总的时间复杂度为 O(n)
空间复杂度
每次递归需要 O(1) 空间，递归深度为H，总的空间复杂度为 O(H)，H 为二叉搜索树的深度。
迭代优化
使用递归，结构更加清晰。关于递归的缺点，和二叉树的迭代实现细节可以参考：c++迭代实现二叉树遍历 | 编程之禅
递归的另一个缺点就是，当找到了需要交换的两个节点之后，并不会马上退出递归函数，它需要遍历完所有节点才会退出。使用迭代实现，当找到需要交换的两个节点之后可以马上退出。
具体代码如下：
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
| class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* x = nullptr;
TreeNode* y = nullptr;
TreeNode* pre = nullptr;
stack<TreeNode*>s;
while(root!=nullptr || !s.empty()){
while(root!=nullptr){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if(pre != nullptr && root->val < pre->val){
y = root;
if(x==nullptr){
x = pre;
}else
break;
}
pre = root;
root = root->right;
}
swap(x->val,y->val);
}
};
|
时间复杂度和空间复杂度和 递归版本一致
Morris 中序遍历
Morris 中序遍历可以实现O(1) 的空间复杂度，即它不需要一个栈来存储递归路径。它的原理就是，对于它的每一个子树，只要它的左孩子存在，就将其左子树中序遍历的最后一个节点(前驱节点)的右孩子指向子树根节点，这样当遍历完左子树的时候，可以回到子树根节点。回到根节点后，根据它的前驱节点的右孩子是否为空，判断它的右孩子是否访问过，如果为空，代表它的右孩子还没访问，如果不为空，表示它的右孩子已经访问过，此时将它的前驱节点的右孩子置为空，恢复为原来的结构。
具体代码如下：
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
| class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* x = nullptr;
TreeNode* y = nullptr;
TreeNode* pre = nullptr;
TreeNode* predecessor = nullptr;
while(root!=nullptr){
if(root->left!=nullptr){
predecessor = root->left;
while(predecessor->right!=nullptr && predecessor->right!=root){
predecessor = predecessor->right;
}
if(predecessor->right == nullptr){
predecessor->right = root;
root = root->left;
}else{
if(pre!=nullptr && root->val < pre->val){
y = root;
if(x==nullptr){
x = pre;
}
}
pre = root;
predecessor->right = nullptr;
root = root->right;
}
}else{
if(pre!=nullptr && root->val < pre->val){
y = root;
if(x==nullptr){
x = pre;
}
}
pre = root;
root = root->right;
}
}
swap(x->val,y->val);
}
};
|
时间复杂度
每个节点被访问了两次，因此时间复杂度为 O(2N)=O(N)，N 为节点个数。
空间复杂度
O(1)
