8000 3 · javasharper/leetcode@46cec25 · GitHub
[go: up one dir, main page]
Skip to content

Commit 46cec25

Browse files
kedebugkedebug
committed
3
1 parent 26b1a32 commit 46cec25

File tree

1 file changed

+33
-45
lines changed

1 file changed

+33
-45
lines changed

‎RecoverBinarySearchTree/RecoverBinarySearchTree.cpp

Lines changed: 33 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,56 +1,44 @@
1-
/**
2-
* Definition for binary tree
3-
* struct TreeNode {
4-
* int val;
5-
* TreeNode *left;
6-
* TreeNode *right;
7-
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8-
* };
9-
*/
1+
// O(n) time, O(1) space
102
class Solution {
113
public:
124
void recoverTree(TreeNode *root) {
13-
// Start typing your C/C++ solution below
14-< 10000 div class="diff-text-inner"> // DO NOT write int main() function
5+
TreeNode* node = root;
6+
TreeNode* prev = NULL;
7+
TreeNode* prev1 = NULL;
8+
TreeNode* curr1 = NULL;
9+
TreeNode* prev2 = NULL;
10+
TreeNode* curr2 = NULL;
1511

16-
TreeNode *parent = NULL;
17-
TreeNode *current = root;
18-
TreeNode *mistake_node1 = NULL;
19-
TreeNode *mistake_node2 = NULL;
20-
21-
while (current != NULL) {
22-
if (current->left == NULL) {
23-
if (parent && parent->val > current->val) {
24-
if (mistake_node1 == NULL)
25-
mistake_node1 = parent;
26-
mistake_node2 = current;
12+
while (node != NULL) {
13+
if (node->left == NULL) {
14+
prev = node;
15+
node = node->right;
16+
} else {
17+
TreeNode* next = node->left;
18+
while (next->right && next->right != node) {
19+
next = next->right;
2720
}
28-
parent = current;
29-
current = current->right;
30-
}
31-
else {
32-
TreeNode *prev = current->left;
33-
while (prev->right && prev->right != current)
34-
prev = prev->right;
35-
36-
if (prev->right == NULL) {
37-
prev->right = current;
38-
current = current->left;
21+
if (next->right == NULL) {
22+
next->right = node;
23+
node = node->left;
24+
} else {
25+
prev = node;
26+
node = node->right;
27+
next->right = NULL;
3928
}
40-
else {
41-
if (parent->val > current->val) {
42-
if (mistake_node1 == NULL)
43-
mistake_node1 = parent;
44-
mistake_node2 = current;
45-
}
46-
prev->right = NULL;
47-
parent = current;
48-
current = current->right;
29+
}
30+
if (prev && node && prev->val > node->val) {
31+
if (prev1 == NULL) {
32+
prev1 = prev, curr1 = node;
33+
} else {
34+
prev2 = prev, curr2 = node;
4935
}
5036
}
5137
}
52-
if (mistake_node1 && mistake_node2)
53-
swap(mistake_node1->val, mistake_node2->val);
38+
if (prev1 && curr2) {
39+
swap(prev1->val, curr2->val);
40+
} else {
41+
swap(prev1->val, curr1->val);
42+
}
5443
}
5544
};
56-
// http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html

0 commit comments

Comments
 (0)
0