2014
06-13

# LeetCode-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?

2 3 4 5 6 7 8

2 6 4 5 3 7 8

#include <iostream>
using namespace std;

/* 二叉树节点 */
struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
};

struct TreeNode* newNode(int data)
{
struct TreeNode * node = new struct TreeNode;
node->val = data;
node->left = NULL;
node->right = NULL;
return(node);
}

class Solution {
public:
TreeNode * pre, * first, * last;
void recoverTree(TreeNode *root) {
pre = first = last = NULL;
inOrder(root);
swap(first->val, last->val);
}
void inOrder(TreeNode * root){
if(!root) return;
inOrder(root->left);
if(pre&& pre->val > root->val)
{
if(first == NULL)//first必须为最左边的
first = pre;
last = root;
}
pre=root;
inOrder(root->right);
}

};

void inOrderTra(TreeNode * root){
if(root == NULL) return;
inOrderTra(root->left);
cout << root->val << " ";
inOrderTra(root->right);
}

//测试
int main()
{
/*  创建以下的树
6
/   \
4      7
/  \    /
3     5  8
/
2

*/
struct TreeNode *root = newNode(6);
root->left        = newNode(4);
root->right       = newNode(8);
root->left->left  = newNode(3);
root->left->left->left  = newNode(2);
root->left->right = newNode(5);
root->right->left = newNode(7);

//中序遍历
inOrderTra(root);
cout << endl;

//交换3和6
root->left->left->val = 6;
root->val = 3;
//中序遍历
inOrderTra(root);
cout << endl;

Solution s;
s.recoverTree(root);
//中序遍历
inOrderTra(root);
cout << endl;
return 0;
}

1. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

2. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

3. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

4. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

5. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

6. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

7. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

8. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

9. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

10. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

11. 真也好假也好，夸也好骂也好，把舆论炸起来，让更多人进来搞总是好的，不然就靠北汽和BYD，等到这届核心下去怕也成不了增长点

12. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}