题目简介：
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
|
示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
|
思路：
由于是二叉搜索树，所以其中序遍历必是一个递增序列。
所以我们对其进行中序遍历，并在过程中保存当前结点的前驱结点(即在中序遍历中上一个被访问到的节点)。
若root -> val < pre -> val，则说明此处发生了错误，并且值较大的结点，即pre结点就是我们需要换的一个结点，而root结点不一定是最终要换的结点(存在[3, 2, 1]的情况)。
若第二次发生root -> val < pre -> val，由于只有两个结点发生错误，所以此时的root结点即为另一个所需交换的结点。
最后交换上述两个结点的val即可。
tip:
代码如下：
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
|
class Solution {
public:
void recoverTree(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* pre = nullptr;
TreeNode* swap_left = nullptr;
TreeNode* swap_right = nullptr;
while(!stk.empty() || root){
while(root){
stk.push(root);
root = root -> left;
}
root = stk.top();
stk.pop();
if(pre && root -> val < pre -> val){
swap_right = root;
if(!swap_left)
swap_left = pre;
else
break;
}
pre = root;
root = root -> right;
}
swap(swap_left -> val, swap_right -> val);
}
};
|
