二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 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
|
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
方法一：显式中序遍历
我们知道 BST 的中序遍历是有序的，我们可以使用一个数组存储中序遍历的结点。在交换了两个结点之后的数组，如果我们将其画成折线图，我们会发现存在一段或两段 “下降” 的折线。下面看几个示例：
1
2
3
4
| 交换两个结点后的中序遍历序列:
[1, 3, 2, 4], 存在一段下降的折线[3, 2]，我们交换 “3” 和 “2” 即可
[1, 5, 3 ,4 ,2 ,6], 存在两段下降的折线[5, 3] 和[4, 2]，我们交换左边折线的结点“5” 和右边折线的结点 “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
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public void recoverTree(TreeNode root) {
List<TreeNode> nodes = new ArrayList<TreeNode>();
inOrder(root, nodes);
int n = nodes.size();
int i = 0, j = n - 1;
for(; i < n - 1; i++){
if(nodes.get(i).val > nodes.get(i + 1).val){
break;
}
}
for(; j > 0; j--){
if(nodes.get(j).val < nodes.get(j - 1).val){
break;
}
}
TreeNode n1 = nodes.get(i);
TreeNode n2 = nodes.get(j);
int temp = n1.val;
n1.val = n2.val;
n2.val = temp;
}
public void inOrder(TreeNode root, List<TreeNode> nodes){
if(root == null){
return;
}
inOrder(root.left, nodes);
nodes.add(root);
inOrder(root.right, nodes);
}
}
|
空间复杂度O(n)，时间复杂度O(n)。
方法二：隐式中序遍历
在方法一中，我们使用了一个数组来保存中序遍历的结点，我们可以在中序遍历的过程中找到两个交换的结点，从而避免了存储中序遍历的结点。
我们使用 pre 来指向前一个遍历的结点，pre.val > root.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
| class Solution {
TreeNode x = null;
TreeNode y = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = x.val;
x.val = y.val;
y.val = temp;
}
private void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
if(x == null && pre.val > root.val){
x = pre;
}
if(x != null && pre.val > root.val){
y = root;
}
pre = root;
inOrder(root.right);
}
}
|
空间复杂度O(h)，h 为二叉树的高度。时间复杂度O(n)。
方法三：Morris 中序遍历
Morris 非递归中序遍历空间复杂度可以降为O(1)。
Morris 遍历算法步骤如下（假设当前遍历到的结点为 x ）：
- 如果 x 无左孩子，则访问 x 的右孩子， 即 x = x.right。
- 如果 x 有左孩子，则找到 x 左子树上的最右结点（即左子树中序遍历的最后一个结点，x 在中序遍历的前驱结点），记为 predecessor。根据 predecessor的右孩子是否为空，进行如下操作：
- 如果 predecessor的右孩子为空，将其右孩子指向 x ，然后访问 x 的左孩子，即 x = x.left。
- 如果 predecessor的右孩子不为空，则此时其右孩子指向 x ，说明我们已经遍历完 x 的左子树，我们将 predecessor的右孩子置空，然后访问 x 的右孩子，即 x = x.right。
重复上述操作，直至访问完整棵树。
整个过程我们只多做一步：将当前结点左子树中的最右边的结点指向它，这样在左子树遍历完成后，我们可以通过这个指针回到 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public void recoverTree(TreeNode root) {
TreeNode x = null, y = null, pred = null, predecessor = null;
while(root != null){
if(root.left != null){
predecessor = root.left;
while(predecessor.right != null && predecessor.right != root){
predecessor = predecessor.right;
}
if(predecessor.right == null){
predecessor.right = root;
root = root.left;
}
else{
if(pred != null && root.val < pred.val){
y = root;
if(x == null){
x = pred;
}
}
pred = root;
predecessor.right = null;
root = root.right;
}
}
else{
if(pred != null && root.val < pred.val){
y = root;
if(x == null){
x = pred;
}
}
pred = root;
root = root.right;
}
}
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
|
时间复杂度O(n)，空间复杂度O(1)。
参见王尼玛的幻灯片更好地理解算法过程。