Morris 遍历

6/3, Tree, Morris 遍历

这个帖子 的描述和代码非常好，还有这个。

我一开始以为 Morris 遍历会改变原树的结构所以不能用，后来发现并不会。。。于是这种技巧还是很值得掌握的。

1968年，Knuth提出说能否将该问题的空间复杂度压缩到O(1)，同时原树的结构不能改变。大约十年后，1979年，Morris在《Traversing Binary Trees Simply and Cheaply》这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

每次访问root左子树之前，先找到左子树里面最右面的点，并把其 right 指针连到 root 上；左子树遍历完这个点之后，再把这个多出来的指针拆掉。

Morris in-order 流程，利用 threaded binary tree.

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode cur = root;
        while(cur != null){
            if(cur.left == null){
                list.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur){
                    prev = prev.right;
                }
                if(prev.right == null){
                    prev.right = cur;
                    // Uncomment for pre-order
                    // list.add(cur.val);
                    cur = cur.left;
                } else {
                    prev.right = null;
                    // Uncomment for in-order
                    // list.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return list;
    }
}

于是这道要求用 O(n) 时间 O(1) 空间的题就可以真正按照题目要求解决了。

Recover Binary Search Tree

public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode prevNode = null;
        TreeNode p = null;
        TreeNode q = null;

        while(cur != null){
            if(cur.left == null){
                if(prevNode != null && prevNode.val >= cur.val){
                    if(p == null) p = prevNode;
                    q = cur;
                }
                // Set prev node for scanning
                prevNode = cur;
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur){
                    prev = prev.right;
                }
                if(prev.right == null){
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;

                    if(prevNode != null && prevNode.val >= cur.val){
                        if(p == null) p = prevNode;
                        q = cur;
                    }
                    // Set prev node for scanning
                    prevNode = cur;
                    cur = cur.right;
                }
            }
        }

        swap(p, q);
    }

    private void swap(TreeNode p, TreeNode q){
        if(p == null || q == null) return;
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}

Morris 的 post-order 遍历还要建一个 dummy node 以及反序输出。。感觉不是非常现实。。。有空复习的时候我再研究研究这种 trick 吧。