题目：

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?

 

题解：

 解决方法是利用中序遍历找顺序不对的两个点，最后swap一下就好。

 因为这中间的错误是两个点进行了交换，所以就是大的跑前面来了，小的跑后面去了。

 所以在中序便利时，遇见的第一个顺序为抵减的两个node，大的那个肯定就是要被recovery的其中之一，要记录。

 另外一个，要遍历完整棵树，记录最后一个逆序的node。

 简单而言，第一个逆序点要记录，最后一个逆序点要记录，最后swap一下。

 因为Inorder用了递归来解决，所以为了能存储这两个逆序点，这里用了全局变量，用其他引用型遍历解决也可以。

 

代码如下：

 

 1 

public 

class Solution {

 2     TreeNode pre;

 3     TreeNode first;

 4     TreeNode second;

 5       

 6     

public 

void inorder(TreeNode root){  

 7         

if(root == 

null)  

 8             

return;  

 9 

10         inorder(root.left);  

11         

if(pre == 

null){  

12             pre = root;  

//

pre指针初始

13 

        }

else{  

14             

if(pre.val > root.val){  

15                 

if(first == 

null){  

16                     first = pre;

//

第一个逆序点

17 

                }  

18                 second = root;  

//

不断寻找最后一个逆序点

19 

            }  

20             pre = root;  

//

pre指针每次后移一位

21 

        }  

22         inorder(root.right);  

23     }  

24       

25     

public 

void recoverTree(TreeNode root) {  

26         pre = 

null;  

27         first = 

null;  

28         second = 

null;  

29         inorder(root);  

30         

if(first!=

null && second!=

null){   

31             

int tmp = first.val;  

32             first.val = second.val;  

33             second.val = tmp;  

34         }  

35     }