题目描述
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
题解
中序遍历，结果中如果有一个降序对，说明该两个node需交换；若有两个降序对，说明第一对的前一个node和第二对的后一个node需要交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void midtravel2(TreeNode* root,vector<TreeNode*>& v)
{
if (root == NULL)return;
midtravel2(root->left,v);
if (!v.empty())
if (v[v.size()-1]->val<root->val)
v.pop_back();
else
v.push_back(root);
v.push_back(root);
midtravel2(root->right,v);
}
void recoverTree(TreeNode* root) {
vector<TreeNode*> v;
midtravel2(root,v);
int vs = v.size();
if (v[vs - 1]->val > v[vs - 2]->val) {
v.pop_back(); vs--;
}
int t1 = v[0]->val;
v[0]->val = v[vs- 1]->val;
v[vs - 1]->val = t1;
}
|
执行用时 :44 ms, 在所有 C++ 提交中击败了16.36%的用户
内存消耗 :17.7 MB, 在所有 C++ 提交中击败了63.97%的用户
这效率也太垃圾了。
要求O(1)空间，采用 Morris遍历。学吧。
今天不太想写。复制代码了。https://www.jianshu.com/p/484f587c967c
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
|
public class MorrisTraval {
private TreeNode root = null;
public MorrisTraval(TreeNode r) {
this.root = r;
}
public void travel() {
TreeNode n = this.root;
while (n != null) {
if (n.left == null) {
System.out.print(n.vaule + " ");
n = n.right;
} else {
TreeNode pre = getPredecessor(n);
if (pre.right == null) {
pre.right = n;
n = n.left;
}else if (pre.right == n) {
pre.right = null;
System.out.print(n.vaule + " ");
n = n.right;
}
}
}
}
private TreeNode getPredecessor(TreeNode n) {
TreeNode pre = n;
if (n.left != null) {
pre = pre.left;
while (pre.right != null && pre.right != n) {
pre = pre.right;
}
}
return pre;
}
}
|
getPredecessor 作用是获得给定节点的前序节点，travel 接口做的就是前面描述的算法步骤，在while循环中，进入一个节点时，先判断节点是否有左孩子，没有的话就把节点值打印出来，有的话，先获得前序节点，然后判断前序节点的右孩子指针是否指向自己，是的话把自己的值打印出来，进入右孩子，前序孩子的右孩子指针是空的话，就把右孩子指针指向自己，然后进入左孩子。
Morris遍历，由于要把前缀节点的右指针指向自己，所以暂时会改变二叉树的结构，但在从前缀节点返回到自身时，算法会把前缀节点的右指针重新设置为空，所以二叉树在结构改变后，又会更改回来。
在遍历过程中，每个节点最多会被访问两次，一次是从父节点到当前节点，第二次是从前缀节点的右孩子指针返回当前节点，所以Morris遍历算法的复杂度是O(n)。在遍历过程中，没有申请新内存，因此算法的空间复杂度是O(1).