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?

 

confused what "{1,#,2,3}" means? 

 

Hide Tags

   

 

 

思路：

O(n) 空间的解法是，开一个指针数组，中序遍历，将节点指针依次存放到数组里，然后寻找两

处逆向的位置，先从前往后找第一个逆序的位置，然后从后往前找第二个逆序的位置，交换这两个

指针的值。

中序遍历一般需要用到栈，空间也是 O(n) 的，如何才能不使用栈？Morris 中序遍历。

 

方法一：中序遍历

class Solution {    public:        void recoverTree(TreeNode *root) {            vector
     
       result;            stack
      
        st;            TreeNode* p = root;            // inorder traverse            while(p != NULL || st.size() != 0)            {                while(p != NULL)                {                    st.push(p);                    p = p->left;                }                if(!st.empty())                {                    p = st.top();                    st.pop();                    result.push_back(p);                    p = p->right;                }            }            TreeNode* r1 = NULL, *r2 = NULL;            for(int i = 0; i < result.size()-1; i++)            {                if(result[i]->val  > result[i+1]->val)                {                    r1 = result[i];                    break;                }            }            for(int i = result.size()-1; i >= 1; i--)            {                if(result[i]->val < result[i-1]->val)                {                    r2 = result[i];                    break;                }            }            //swap r1 and r2's value            int tmp = r1->val;            r1->val = r2->val;            r2->val = tmp;        }};