# 99. Recover Binary Search Tree 原

cofama

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?

``````class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* prev = NULL;
TreeNode* tmp = NULL;
TreeNode* first = NULL;
TreeNode* second = NULL;
while(root!=NULL) {
if(root->left!=NULL) {
tmp = root->left;
while(tmp->right!=NULL && tmp->right!=root) tmp = tmp->right;
if(tmp->right==NULL) {
tmp->right = root;
root = root->left;
}
else {
tmp->right = NULL;
//find wrong elements
if(first==NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
else {
//find wrong elements
if(first==NULL && prev!=NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
//swap
int temp = first->val;
first->val = second->val;
second->val = temp;
}
};
``````

### cofama

LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自： https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0

http://acm.nyist.net/JudgeOnline/problem.php?pid=221 输入 The input will contain one or more test cases. Each test case consists of one line containing two strings preord and i......

2017/02/24
0
0
Leetcode 669. Trim a Binary Search Tree

xgnming
09/06
0
0
ZOJ Problem Set - 1944 Tree Recovery(二叉树三种遍历知二求三）

Tree Recovery Time Limit: 2 Seconds Memory Limit: 65536 KB Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary......

hushhw
2017/11/27
0
0
Leetcode 700. Search in a Binary Search Tree

SnailTyan
08/07
0
0

72.告警系统邮件引擎 运行告警系统

20.23/20.24/20.25 告警系统邮件引擎 20.26 运行告警系统 20.23/20.24/20.25 告警系统邮件引擎 邮件首先要有一个mail.py，以下。 因为我们之前zabbix的时候做过，就可以直接拷贝过来 mail.s...

44分钟前
1
0
09-利用思维导图梳理JavaSE-

09-利用思维导图梳理JavaSE-Java IO流 主要内容 1.Java IO概述 1.1.定义 1.2.输入流 - InputStream 1.3.输出流 - OutputStream 1.4.IO流的分类 1.5.字符流和字节流 2.InputStream类 2.1.File...

50分钟前
3
0
Spring Cloud 微服务的那点事

59分钟前
2
0

Java干货分享

1
0
gson1.7.1线程并发导致空指针问题