Morris 遍歷實現二元樹的遍歷

作者：Grey

原文地址：

部落格園：Morris 遍歷實現二元樹的遍歷

CSDN：Morris 遍歷實現二元樹的遍歷

說明

Morris 遍歷可以實現二元樹的先，中，後序遍歷，且時間複雜度O(N), 空間複雜度可以做到O(1)。

Morris 遍歷流程

假設有一棵如下的二元樹

Morris遍歷的流程主要分如下幾個步驟：

第一步，從頭節點開始遍歷。

第二步，假設當前遍歷的節點是cur。

第三步，如果cur無左樹, cur來到其右樹上，即：cur = cur.right

第四步，如果cur有左樹，找到cur左樹最右節點，假設叫mostRight，則有如下兩種小情況：

情況1，如果mostRight的右指標指向空, 則將mostRight的右指標指向cur，即：mostRight.right = cur, 然後將cur向左移動，即：cur = cur.left，

情況2，如果mostRight的右指標指向當前節點cur，則將mostRight的右指標指向空，即：mostRight.right = null，然後將cur向右移動，即：cur = cur.right。

第五步：當cur = null，遍歷結束。

根據如上流程，範例二元樹的Morris遍歷序列為：

1-->2-->4-->7-->11-->7-->4-->8-->12-->8-->1-->3-->5-->3-->6-->9-->13-->6-->10

Morris遍歷可以實現在O(N)時間複雜度內，用O(1)的空間複雜度實現對樹的遍歷，而且，只要某個節點有右樹，則這個節點一定會被遍歷兩次，我們可以通過Morris遍歷來實現二元樹的先，中，後序遍歷，做到時間複雜度O(N)，空間複雜度O(1)。

程式碼實現如下：

public class Code_Morris {

    //當前是cur
    //1. cur無左樹,cur = cur.right
    //2. cur有左樹,找到左樹最右節點mostRight
    //	a. mostRight的右指標指向null, mostRight.right = cur, cur = cur.right
    //	b. mostRight的右指標指向當前節點cur，mostRight.right = null, cur = cur.right
    //3. cur = null 停
    public static void morrisPrint(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.println("....morris order....");
        TreeNode cur = head;
        System.out.print(cur.val + "-->");
        TreeNode mostRight;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    System.out.print(cur.val + "-->");
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
            if (cur != null) {
                System.out.print(cur.val + "-->");
            }
        }
    }
}

Morris遍歷實現先序遍歷

根據Morris的遍歷結果，沒有右樹的點只會遍歷一次，有右樹的點會遍歷兩次，針對遍歷一次的點，遍歷到就收集，針對遍歷兩次的點，第一次遍歷到就收集，第二次遍歷到不收集，整個流程跑完，則得到了先序遍歷的結果。

程式碼如下：

    public static List<Integer> preorderTraversal(TreeNode root) {
        if (null == root) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        TreeNode mostRight;
        TreeNode cur = root;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 有右樹，第一次來到自己就收集
                    ans.add(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // mostRight.right = cur;
                    mostRight.right = null;
                }
            } else {
                // 沒有右樹的，來到就收集
                ans.add(cur.val);
            }
            cur = cur.right;
        }
        return ans;
    }

測評連結：LeetCode 144. Binary Tree Preorder Traversal

Morris遍歷實現中序遍歷

針對遍歷一次的點，遍歷到就收集，針對遍歷兩次的點，第一次遍歷到不收集，第二次遍歷才收集，整個流程跑完，則得到了中序遍歷的結果。

程式碼如下：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        TreeNode mostRight;
        TreeNode cur = root;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 來到自己兩次的點，第二次來到才收集
                    ans.add(cur.val);
                    mostRight.right = null;
                }
            } else {
                // 只來到自己一次的點，來到就收集
                ans.add(cur.val);
            }
            cur = cur.right;
        }
        return ans;
    }
}

測評連結：LeetCode 94. Binary Tree Inorder Traversal

Morris遍歷實現後序遍歷

Morris遍歷實現後序遍歷相對比較麻煩，處理時機只放在能回到自己兩次的點，能回到自己兩次的點在第二次回到自己的時刻，不列印它自己，而是逆序列印他左樹的右邊界, 整個遍歷結束後，單獨逆序列印整棵樹的右邊界，即得到了後序遍歷的結果。

程式碼如下：

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        TreeNode cur = root;
        TreeNode mostRight;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                    // 第二次來到自己的時候，收集自己的左樹的右邊界
                    collect(cur.left, ans);
                }
            }
            cur = cur.right;
        }
        collect(root, ans);
        return ans;
    }

    private void collect(TreeNode root, List<Integer> ans) {
        TreeNode node = reverse(root);
        TreeNode c = node;
        while (c != null) {
            ans.add(c.val);
            c = c.right;
        }
        reverse(node);
    }

    private TreeNode reverse(TreeNode node) {
        TreeNode pre = null;
        TreeNode cur = node;
        while (cur != null) {
            TreeNode t = cur.right;
            cur.right = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }

需要注意兩點：

第一點，collect方法即逆序收集左樹的有邊界，由於每個節點沒有指向父的指標，所以，要實現逆序，需要針對右邊界採用反轉連結串列的方式。即reverse函數的邏輯。

第二點，在collect方法呼叫完反轉連結串列操作後，還要還原整個右邊界。否則整棵樹的指標就指亂了。

測評連結：LeetCode 145. Binary Tree Postorder Traversal

更多

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲