1.题目描述

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.解法分析

对有异常的BST进行pre-order的遍历，遍历过程中第一次发现相邻元素的逆序，即前一个元素值比后一个节点的元素值大，那么前一个节点是被交换的节点中的其中一个，记为sw1，继续遍历，找到第一个比sw1中元素值大的节点sw2,如果找到，sw1和sw2，交换它们的元素值即可。细节参考代码。

/**

* 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

vector
           
             v;
           

TreeNode * curTN=root;

TreeNode *prevTN=NULL;

TreeNode *sw1=NULL;

TreeNode *sw2=NULL;

while(!v.empty()||curTN)

{

while(curTN)

{

v.push_back(curTN);

curTN=curTN->left;

}

if(!v.empty())

{

curTN =v.back();v.pop_back();

if(!sw1){

if(!prevTN){

prevTN=curTN;

}

else

{

if(curTN->val
           
            val){
           

sw1=prevTN;

}

prevTN =curTN;

}

}

else

{

if(curTN->val>sw1->val){sw2=prevTN;break;}

else prevTN=curTN;

}

curTN = curTN->right;

}

}

if(!sw1)return; //未找到异常交换

if(!sw2)sw2=prevTN;//最大的一个节点被交换

int temp=sw1->val;

sw1->val=sw2->val;

sw2->val=temp;

}

};

 

另外题目说不用O(N)的空间复杂度会有加分，在discuss里面找了一个，没仔细看，思路大概跟我的一样，但是就是记录路径可能用了不同的办法，貌似叫做，代码如下，做个记录，之后再分析（今天写了一篇文章，详细介绍了)：

/**

* 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 *h) {

TreeNode *f1, *f2;

bool found = false;

TreeNode *pre, *par = 0; // previous AND parent

while(h) { // Morris Traversal

if(h->left == 0) {

if(par && par->val > h->val) {  // inorder previous is: par

if(!found) {

f1 = par;

found = true;

}

f2 = h;

}

par = h;

h = h->right;

continue;

}

pre = h->left;

while(pre->right != 0 && pre->right != h)

pre = pre->right;

if(pre->right == 0) {

pre->right = h;

h = h->left;

} else {

pre->right = 0;

if(pre->val > h->val) { // inorder previous is: pre

if(!found) {

f1 = pre;

found =true;

}

f2 = h;

}

par = h;

h = h->right;

}

}

if(found)

swap(f1->val, f2->val);

}

};