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?

---

constant space resolution: Morris Traversal or Morris Threading Traversal.

也是用中序遍历的思想，找那个元素不是递增。Morris traversal用threaded binary tree进行中序遍历，只要Ｏ(1)的空间复杂度。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void recoverTree(TreeNode root) {        TreeNode cur = root, prev = null, n1 = null, n2 = null, last = null;        while (cur != null) {            prev = cur.left;            if (prev == null) { // visit current node                if (last != null && cur.val < last.val) {                    if (n1 == null) {                        n1 = last;                        n2 = cur;                    } else {                        n2 = cur;                    }                }                last = cur;                cur = cur.right; // jump to its next                continue;            }            while (true) {                if (prev.right == null) {                    prev.right = cur;                    cur = cur.left;                    break;                } else if (prev.right == cur) { // visit current node                    prev.right = null;                    if (cur.val < last.val) {                        if (n1 == null) {                            n1 = last;                            n2 = cur;                        } else {                            n2 = cur;                        }                    }                    last = cur;                    cur = cur.right;                    break;                }                prev = prev.right;            }        }        int tmp = n1.val;        n1.val = n2.val;        n2.val = tmp;    }}

 

只会straight forward的Ｏ（n)解法：ＢＳＴ的中序遍历应该是递增的，对给的树中序遍历，如果碰到递减的元素，记下来，说明是被交换过的。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void recoverTree(TreeNode root) {        Stack
     
       stack = new Stack
      
       ();        TreeNode n1 = null, n2 = null, n3 = null, cur = root, prev = null, tmp = null;        while (cur != null) {            stack.push(cur);            cur = cur.left;        }        while (!stack.empty()) {            cur = stack.pop();            if (prev != null && cur.val < prev.val) {                if (n1 == null) {                    n1 = prev;                    n2 = cur;                } else {                    n2 = cur;                    break;                }            }            prev = cur;            tmp = cur.right;            while (tmp != null) {                stack.push(tmp);                tmp = tmp.left;            }        }        // should find the parent of n1 and n2 instead of swapping values？        int v1 = n1.val;        n1.val = n2.val;        n2.val = v1;    }}