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?

>
read more on how binary tree is serialized on OJ.

这里有几个知识点能够注意一下。是个不错的考察BST的题目。

一、要怎样找出这两个有乱序的位置呢？假设直接在树上考察，似乎关系有些模糊；那么，考虑一个性质。通过中序遍历，能够将BST按升序输出，eg：12
3 4 56 7，这里随意调换一下位置。构成16 3 4 5 2 7, 6 和
2将数列切割成了三份。每份独立时仍然保持升序（有能够能头尾的部门不包括元素），可是6 > 3。 5 > 2；说明，第一次出现 pre > cur的情况。pre是那个错误节点。第二次出现 pre > cur的情况。cur是错误节点，记录下来就能够了。

二、有可能调换位置的元素在排序中相邻（树结构图中不一定相邻），一中提到的pre >cur的情况就发生重合，仅仅有一次；

代码例如以下：

class Solution {

private:

TreeNode *Pre, *node1, *node2;  //申明为成员变量，这样每一个函数都能够訪问，不必反复创建；

void inOrder(TreeNode *root){

    if (root == NULL)

        return;

    inOrder(root->left);

    if (Pre != NULL && Pre->val > root->val){  //第二次（也是最后一次）出现的才是正确位置。这里这样写避免了推断，直接覆盖

        node2 = root;

        if (node1 == NULL)             //利用 NULL 为是否为第一次出现的标记

            node1 = Pre;

    }

    Pre = root;

    inOrder(root->right);

}

public:

    void recoverTree(TreeNode *root) {

        Pre = NULL;

        node2 = node1 = NULL;

        inOrder(root);

        node1->val ^= node2->val;

        node2->val ^= node1->val;

        node1->val ^= node2->val;

    }

};