Recovery Binary Search Tree

Question

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?

Solution

第一次自己寫就有解出來，只是做法比較醜，純粹使用 in-order traversal 再去 swap 即可。但有另一個思路是 Morris Traversal，適用的情況是在：

1. space complexity 要 O(1)
2. 不能改變原來的 tree structure

這個演算法想探討的問題在於：該用什麼方法回到 current node？recursion 在 return 的時候會自己回到上一層，而用 stack 也可以透過 pop, push 得到回去的路。但因為這兩個方法都是用到 O(n) space complexity，因此不是用在這個題目上。Morris Traversal 的方法是，對於每個 current node，你先去找到它的 predecessor，什麼意思呢？就是判斷他如果有 left child，那就找 left child 的 right-most node，這個就是當 in-order traversal 完 left subtree 後的最後一個 visit node，如果把這個 node.right = current node，就有了一條回去的路。

    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }    

        TreeNode first = null;
        TreeNode second = null;
        TreeNode prev = null;

        while (root != null) {
            if (root.left == null) {
                if (prev != null && prev.val >= root.val) {
                    if (first == null) {
                        first = prev;
                        second = root;
                    } else {
                        second = root;
                    }
                }

                prev = root;
                root = root.right;
            } else {
                TreeNode temp = root.left;
                //先走到 left subtree 的最右邊那個 node
                while (temp.right != root && temp.right != null) {
                    temp = temp.right;
                }

                //代表沒有被 visited, 所以設 left subtree 最右邊的 node 的 right 為 root, 整棵樹往 root.left 遍歷
                if (temp.right == null) {
                    //connecting 
                    temp.right = root;
                    root = root.left;
                } else { //代表已經被 visited, 所以把 left subtree 最右邊的 node 的 right reset 回 null, 並往 root.right 遍歷
                    if (prev != null && prev.val >= root.val) {
                        if (first == null) {
                            first = prev;
                            second = root;
                        } else {
                            second = root;
                        }
                    }
                    temp.right = null;
                    prev = root;
                    root = root.right;
                }
            }
        }

        int t = first.val;
        first.val = second.val;
        second.val = t;
    }

單純用 Morris Traversal 來做 in-order traversal

    public void morrisTraversal(TreeNode root){
        TreeNode temp = null;
        while(root!=null){
            if(root.left!=null){
                // connect threading for root
                temp = root.left;
                while(temp.right!=null && temp.right != root)
                    temp = temp.right;
                // the threading already exists
                if(temp.right!=null){
                    temp.right = null;
                    System.out.println(root.val);
                    root = root.right;
                }else{
                    // construct the threading
                    temp.right = root;
                    root = root.left;
                }
            }else{
                root = root.right;
            }
        }
    }