-
Notifications
You must be signed in to change notification settings - Fork 15
/
Recover_Binary_Search_Tree.cpp
63 lines (50 loc) · 1.51 KB
/
Recover_Binary_Search_Tree.cpp
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
/*
Author: Timon Cui, timonbaby@163.com
Title: Recover Binary Search Tree
Description:
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Difficulty rating:
Source:
http://www.leetcode.com/onlinejudge
Notes:
In order traversal of a BST should be increasing.
Due to swap of A[i] and A[j], this is no longer true.
E. g. 1 2 3 4 5 --> 1 4 3 2 5
or 1 2 3 4 --> 1 3 2 4
Assume i < j, then A[j] can be found because A[j + 1] < A[j].
A[i] can be found because A[i] < A[i - 1], unless j = i + 1 (second example),
in which case only one such inversion place can be found.
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include "algorithm.hpp"
class Solution {
public:
void recoverTree(TreeNode *root) {
TreeNode *error[2] = {NULL};
TreeNode *pre = NULL;
findInvalid(root, pre, error);
swap(error[0]->val, error[1]->val);
}
private:
void findInvalid(TreeNode *root, TreeNode *&pre, TreeNode *error[2]) {
if (!root) return;
findInvalid(root->left, pre, error);
if (pre && root->val < pre->val) {
if (!error[1]) error[0] = pre;
error[1] = root;
}
pre = root;
findInvalid(root->right, pre, error);
}
};