# LeetCode题目：Recover Binary Search Tree

By | 2012 年 10 月 16 日

<br>
Recover Binary Search Tree
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?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
vector trace;
TreeNode *cur = root;
//find the lest node in the BST
while(cur->left) {
trace.push_back(cur);
cur = cur->left;
}
TreeNode *wrong0 = NULL;//first wrong node
TreeNode *wrong1 = NULL;//last wrong node
while(true){
TreeNode *next = NULL;
//find the next inorder node
if(cur->right){
//if cur have right child, the next inorder node is the most left node in this sub-tree
trace.push_back(cur);
next = cur->right;
while(next->left){
trace.push_back(next);
next = next->left;
}
if(!wrong0 && cur->val > next->val) {
wrong0 = cur;
} else if(wrong0 && wrong0->val <= next->val) {
wrong1 = cur;
break;
}
cur = next;
} else {
//if cur have no right child, the next inorder nodt is the most near parant which cur belong to it's left sub-tree
TreeNode *tempCur = cur;
while(trace.size()) {
TreeNode *tempPar = trace.back();
if(tempPar->left == tempCur) {
next = tempPar;
break;
}
tempCur = tempPar;
trace.pop_back();
}
if(next) {
if(!wrong0 && cur->val > next->val) {
wrong0 = cur;
} else if(wrong0 && wrong0->val <= next->val) {
wrong1 = cur;
break;
}
cur = next;
}
}
if(!next) break;
}
if(!wrong1) wrong1 = cur;
int temp = wrong0->val;
wrong0->val = wrong1->val;
wrong1->val = temp;
}
};
```

Code rewrite at 2013-1-18, 388ms pass large set, more clear

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root) return;
TreeNode *firstNode = NULL, *secondNode = NULL;

//find first node, with inorder traversal
stack trace;
if(root) trace.push(root);
bool forward = true;
TreeNode *pre = NULL;
TreeNode *lastNode = NULL;
while(trace.size()) {
TreeNode *cur = trace.top();
if(forward) {
if(cur->left && cur->left != pre) {
trace.push(cur->left);
} else {
forward = false;
}
} else {
if(pre != cur->right) {
if(lastNode && lastNode->val > cur->val) {
firstNode = lastNode;
break;
}
lastNode = cur;
}
if(cur->right && cur->right != pre) {
trace.push(cur->right);
forward = true;
} else {
trace.pop();
}
}
pre = cur;
}
if(NULL == firstNode) return;

//find second node, in reverse order of inorder traversal
while(trace.size()) trace.pop();
if(root) trace.push(root);
forward = true;
pre = NULL;
lastNode = NULL;
while(trace.size()) {
TreeNode *cur = trace.top();
if(forward) {
if(cur->right && cur->right != pre) {
trace.push(cur->right);
} else {
forward = false;
}
} else {
if(pre != cur->left) {
if(lastNode && lastNode->val < cur->val) {
secondNode = lastNode;
break;
}
lastNode = cur;
}
if(cur->left && cur->left != pre) {
trace.push(cur->left);
forward = true;
} else {
trace.pop();
}
}
pre = cur;
}
if(NULL == secondNode) return;

//swap
int t = firstNode->val;
firstNode->val = secondNode->val;
secondNode->val = t;

}
};
```

## 3 thoughts on “LeetCode题目：Recover Binary Search Tree”

1. nandawys

递归方法 中序遍历二叉树 空间复杂度应该是O(n)
这道题难道是让用非递归的方法遍历吗……

1. uniEagle Post author

是平均logN，最坏N。不知道这题怎么做到常数空间。我的代码就是非递归，但是本质上没有改善空间复杂度。

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
ArrayList t;
TreeNode previous;
public void recoverTree(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
t = new ArrayList();
previous=null;
inorder(root);
int temp = t.get(0).val;
t.get(0).val = t.get(t.size()-1).val;
t.get(t.size()-1).val = temp;
}
public void inorder(TreeNode root) {
if(root==null) return;
inorder(root.left);
if(previous!=null&&previous.val>root.val) {