交换二叉搜索树的两个节点，要求复原。
不确定我的做法对不对，我只是在 value 的程度上把他们复原了。但是原文说不要破坏他们的结构？
想法很简单中序遍历+线性数组纠正
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
class Solution {
public:
void recoverTree(TreeNode *root) {
if(root == NULL)return ;
treeArray.clear();
inOrder(root);
int x,y;
int flag = 0;
for(int i = 0;i < treeArray.size();i++) {
if(i == 0 && treeArray[i] > treeArray[i+1] && i < treeArray.size()-1) {
if(flag == 0) {
x = i;
flag = 1;
}
else {
y = i;
}
continue;
}
if(i == treeArray.size()-1 && treeArray[i] < treeArray[i-1] && i > 0) {
if(flag == 0) {
x = i;
flag = 1;
}
else {
y = i;
}
continue;
}
if( i > 0 && i < treeArray.size()-1 && treeArray[i] > treeArray[i-1] && treeArray[i] > treeArray[i+1]) {
if(flag == 0) {
x = i;
flag = 1;
}
else {
y = i;
}
continue;
}
if( i > 0 && i < treeArray.size()-1 && treeArray[i] < treeArray[i-1] && treeArray[i] < treeArray[i+1] ) {
if(flag == 0) {
x = i;
flag = 1;
}
else {
y = i;
}
continue;
}
}
if(flag == 0) {
for(int i = 0;i < treeArray.size()-1;i++) {
if(treeArray[i] > treeArray[i+1]) {
x = i;
y = i+1;
break;
}
}
}
queryTree(root,x,y);
}
private:
vector<int> treeArray;
void inOrder(TreeNode * root) {
if(root->left != NULL)
inOrder(root->left);
treeArray.push_back(root->val);
if(root->right != NULL)
inOrder(root->right);
}
void queryTree(TreeNode * root,int x,int y) {
if(root->val == treeArray[x]) {
root->val = treeArray[y];
}
else
if (root->val == treeArray[y]){
root->val = treeArray[x];
}
if(root->left != NULL)
queryTree(root->left,x,y);
if(root->right != NULL)
queryTree(root->right,x,y);
}
};
|