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?

思路：使用递归对输入二叉树进行中序遍历。对于二叉搜索树，其中序遍历得到的是一个递增的序列。由于输入二叉搜索树有两个元素被交换了，所以实际我们得到的并不是一个递增的序列。

        假设递增序列：{1,2,3,4,5}，显然，交换两个元素存在两种情况：一种是被交换的两个元素相邻，比如交换1和2，将得到{2,1,3,4,5}；另一种是被交换的两个元素不相邻，比如交换1和3，将得到{3,2,1,4,5}。第一种情况中序遍历序列将出现一个逆序对，即{2,1}；而第二种情况中序遍历序列将出现两个逆序对，即{3,2}和{2,1}。因此，我们只需找出中序遍历序列中的逆序对，便可完成对二叉搜索树的修正。

        为了在递归调用中比较相邻元素，使用全局指针pre指向前一次输出的元素。每次比较当前输出元素与前一次输出元素的大小，若为逆序对，则使用全局指针first和second分别指向它们；若当前逆序对为第二个逆序对，我们只需修改second指针，使它指向当前元素。

 1 class Solution { 2 public: 3     void recoverTree( TreeNode *root ) { 4         prev = first = second = 0; 5         InOrder( root ); 6         if( first ) { swap( first->val, second->val ); } 7         return; 8     } 9 private:10     void InOrder( TreeNode*& node ) {11         if( !node ) { return; }12         InOrder( node->left );13         if( prev && prev->val > node->val ) {14             second = node;15             if( !first ) { first = prev; }16         }17         prev = node;18         InOrder( node->right );19     }20     TreeNode *prev, *first, *second;21 };