morris Traversal

O(n)時間，O(1)空間對二叉樹進行前序、中序、后序遍歷。詳細講解看參考。

public class Solution {

    public static void morrisPreorder(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null) {
            if (cur.left == null) {
                System.out.print(cur.val + " ");
                cur = cur.right;
            } else {
                // find predecessor
                pre = cur.left;
                while (pre.right != null && pre.right != cur)
                    pre = pre.right;

                if (pre.right == null) {
                    System.out.print(cur.val + " ");
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    pre.right = null;
                    cur = cur.right;
                }

            }

        }
        System.out.println();

    }

    public static void morrisInorder(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null) {
            if (cur.left == null) {
                System.out.print(cur.val + " ");
                cur = cur.right;
            } else {
                // find predecessor
                pre = cur.left;
                while (pre.right != null && pre.right != cur)
                    pre = pre.right;

                if (pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;

                } else {
                    pre.right = null;
                    System.out.print(cur.val + " ");
                    cur = cur.right;
                }

            }

        }

        System.out.println();
    }

    public static void morrisPostorder(TreeNode root) {
        TreeNode dump = new TreeNode(0);
        dump.left = root;
        TreeNode cur = dump;
        TreeNode pre = null;

        while (cur != null) {
            if (cur.left == null) {
                cur = cur.right;
            } else {
                // find predecessor
                pre = cur.left;
                while (pre.right != null && pre.right != cur)
                    pre = pre.right;

                if (pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    pre.right = null;
                    printRev(cur.left, pre);
                    cur = cur.right;
                }

            }
        }
        System.out.println();

    }

    private static void printRev(TreeNode from, TreeNode to) {
        reverse(from, to);

        TreeNode p = to;
        while (true) {
            System.out.print(p.val + " ");
            if (p == from)
                break;
            p = p.right;
        }
        reverse(to, from);
    }

    private static void reverse(TreeNode from, TreeNode to) {
        if (from == to)
            return;
        TreeNode pre = from, cur = from.right, post = null;
        while (pre != to) {
            post = cur.right;
            cur.right = pre;
            pre = cur;
            cur = post;
        }

    }

    public static void main(String[] args) {
        String s = "6 2 1 # # 4 3 # # 5 # # 7 # 9 # 8 # #";
        TreeNode root = TreeUtils.makeTree(s);
        TreeUtils.printTree(root);
        morrisPreorder(root);
        morrisInorder(root);
        morrisPostorder(root);

    }

}

復雜度分析：

空間復雜度：O(1)，因為只用了兩個輔助指針。

時間復雜度：O(n)。證明時間復雜度為O(n)，最大的疑惑在于尋找中序遍歷下二叉樹中所有節點的前驅節點的時間復雜度是多少，即以下兩行代碼：

while (pre.right != null && pre.right != cur)
    pre = pre.right;

直覺上，認為它的復雜度是O(nlgn)，因為找單個節點的前驅節點與樹的高度有關。但事實上，尋找所有節點的前驅節點只需要O(n)時間。n個節點的二叉樹中一共有n-1條邊，整個過程中每條邊最多只走2次，一次是為了定位到某個節點，另一次是為了尋找上面某個節點的前驅節點，如下圖所示，其中紅色是為了定位到某個節點，黑色線是為了找到前驅節點。所以復雜度為O(n)。

參考（講的太好了）：

http://www.rzrgm.cn/AnnieKim/archive/2013/06/15/MorrisTraversal.html

posted @ 2014-09-09 22:36 jdflyfly 閱讀(339) 評論(0) 收藏舉報

刷新頁面返回頂部

jdflyfly

morris Traversal

公告