0%

Morris遍历

发表于 分类于

Morris遍历算法

解释:

  1. 记作当前节点为cur, 当前节点的左子树为mostRight
  2. 如果mostRight为空, cur向右移动
  3. 如果不为空, 得到mostRight的最右节点
  4. 如果最右节点的右子节点为空, 设置为cur
  5. 如果最右节点的右子节点为cur, 设置为null

原理:

  1. 每次遍历都将左子树的最右节点的右子树设置为当前节点来缓存, 以便遍历结束后能够回到当前位置.
  2. 因为储存null和储存cur占用空间是相同的, 所以Morris遍历通过这样的方式降低了空间复杂度.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Solution
{
    protected internal class TreeNode
    {
        public TreeNode(int value)
        {
            this.Value = value;
        }
        public int Value { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
    }

    // 先序遍历
    public static void MorrisFront(TreeNode root, Action<int> action)
    {
        if (root == null)
        {
            return;
        }
        TreeNode cur = root;
        while (cur != null)
        {
            TreeNode mostRight = cur.Left;
            if (mostRight != null)
            {
                while (mostRight.Right != null && mostRight.Right != cur)
                {
                    mostRight = mostRight.Right;
                }
                if (mostRight.Right == null)
                {
                    action(cur.Value); // 第一次访问该节点时
                    mostRight.Right = cur;
                    cur = cur.Left;
                    continue;
                }
                mostRight.Right = null;
            }
            else
            {
                action(cur.Value); // 在没有左节点的时候, 第一次和第二次访问该节点的时机合并到一起
            }
            cur = cur.Right;
        }
    }

    // 中序遍历
    public static void MorrisMiddle(TreeNode root, Action<int> action)
    {
        if (root == null)
        {
            return;
        }
        TreeNode cur = root;
        while (cur != null)
        {
            TreeNode 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;
                }
                mostRight.Right = null;
            }
            action(cur.Value); // 第二次访问当前节点
            cur = cur.Right;
        }
    }

    // 后序遍历
    public static void MorrisBack(TreeNode root, Action<int> action)
    {
        if (root == null)
        {
            return;
        }
        void ActionEdge(TreeNode node)
        {
            if (node != null)
            {
                TreeNode tmp1 = node, tmp2 = null;
                while (tmp1.Right != null)
                {
                    TreeNode tmp3 = tmp1.Right;
                    tmp1.Right = tmp2;
                    tmp2 = tmp1;
                    tmp1 = tmp3;
                }
                tmp2 = tmp1;
                while (tmp2 != null)
                {
                    action(tmp2.Value);
                    tmp2 = tmp2.Right;
                }
                while (tmp1.Right != null)
                {
                    TreeNode tmp3 = tmp1.Right;
                    tmp1.Right = tmp2;
                    tmp2 = tmp1;
                    tmp1 = tmp3;
                }
            }
        }
        TreeNode cur = root;
        while (cur != null)
        {
            TreeNode 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;
                }
                mostRight.Right = null;
                ActionEdge(cur.Left); // Morris遍历没法访问节点第三次, 但是我们可以把左子树的右半部分当作链表, 逆序访问就达到第三次访问的目的
            }
            cur = cur.Right;
        }
        ActionEdge(root);// Morris遍历没法访问节点第三次, 但是我们可以把左子树的右半部分当作链表, 逆序访问就达到第三次访问的目的
    }
}

代码解释:

  1. 先序遍历: 当前节点往左移动前, 是第一次访问该节点
  2. 中序遍历: 当前节点往右移动前, 是第二次访问该节点
  3. 后序遍历: 第三次访问该节点只能通过逆序链表, 然后遍历链表来访问
  • 当前节点没有左子树时, 第一次和第二次访问将会被合并为一次
  • 第三次访问节点只能通过间接的方式访问