【题目】
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?
【解析】
O(n) 空间的解法是，开一个指针数组，中序遍历，将节点指针依次存放到数组里，然后寻找两处逆向的位置，
先从前往后找第一个逆序的位置，然后从后往前找第二个逆序的位置，交换这两个指针的值。
【代码】
/*********************************
* 日期：2014-12-10
* 作者：SJF0115
* 题号: Recover Binary Search Tree
* 来源：https://oj.leetcode.com/problems/recover-binary-search-tree/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <malloc.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void InOrder(TreeNode *root){
if(root == NULL){
return;
}
InOrder(root->left);
cout<<root->val<<endl;
InOrder(root->right);
}
class Solution {
public:
void recoverTree(TreeNode *root) {
stack<TreeNode*> stack;
vector<TreeNode*> v;
// 错乱节点
TreeNode *first,*second;
if(root == NULL){
return;
}
TreeNode *p = root;
// 中序遍历
while(p != NULL || !stack.empty()){
// 不空一直向左子树走
if(p){
stack.push(p);
p = p->left;
}
// 转向右子树
else{
p = stack.top();
stack.pop();
v.push_back(p);
p = p->right;
}//if
}//while
// 从前向后遍历
for(int i = 0;i < v.size();i++){
if((v[i])->val > (v[i+1])->val){
first = v[i];
break;
}
}
// 从后向前遍历
for(int i = v.size()-1;i >= 0;i--){
if((v[i])->val < (v[i-1])->val){
second = v[i];
break;
}
}
// 交换错误节点
/*int tmp;
tmp = first->val;
first->val = second->val;
second->val = tmp;*/
swap(first->val,second->val);
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
char data;
//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data-'0';
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
solution.recoverTree(root);
InOrder(root);
}
