算法数据结构

Morris遍历与Morris序

字数统计: 3.3k字   |   阅读时长: 14分
, ,

摘要: 树的 Morris 遍历

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 树的前序、中序、后序遍历与DFS搜索 中，我们知道树的前序、中序和后序遍历都有递归和非递归算法。两者的额外空间都与树的高度 $h$ 有关，空间复杂度为 $O(h)$。

1979 年，Joseph Morris 提出了一种不用栈结构完成三种遍历的算法，额外空间复杂度为 $O(1)$。本文看一下这个算法。

在二叉树的前序、中序、后序遍历的递归、非递归算法中，从下层回到上层是不好解决的难点。这与树的节点的结构有关，每个节点都有指向子节点的指针，但没有指向父结点的指针，因此从下层返回上层需要栈辅助。

因此 Morris 遍历要避免用栈结构，思路就是让下层到上层有指针。具体是通过让底层节点指向 nullptr 的空闲指针指向上层的某个节点，完成下层向上层的移动。

这里的空闲指针是指，如果某个节点 node 没有左子节点，那么 node -> left 就指向 nullptr，那么 node -> left 就是一个空闲指针，右子节点的情况类似。

下面我们首先抛开前序、中序、后序的概念，看一下 Morris 遍历的过程，得到 Morris 序，然后对 Morris 遍历的过程稍微修改即可得到 Morris 前序、Morris 中序、Morris 后序遍历，最后我们用 Morris 遍历解决题目 99. 恢复二叉搜索树。

Morris 遍历与 Morris 序

Morris 遍历算法

设当前节点为 cur，初始时 cur 为树根结点。按以下算法移动 cur：

case1：若 cur 为 nullptr，则移动 cur 的过程停止。

case2：若 cur -> left 为 nullptr，没有左子树，则 cur 向右移动，即 cur = cur -> right。

case3：若 cur -> left 不为空，有左子树，则找到 cur 左子树上的最右节点。记为 precursor。此时根据 precursor -> right 指针决定 cur 向左还是向右移动。

(1) precursor -> right 为 nullptr，则令其指向当前节点，即 precursor -> right = cur。也就是设置 cur 为 precursor -> right 的 Morris 序的后继。然后 cur 向左移动，即 cur = cur -> left。

(2) precursor -> right 指向 cur，则令其指向空，即 precursor -> right = nullptr，此时 cur 的左子树已经遍历完，然后 cur 向右移动，即 cur = cur -> right。

Morris 序

以上图为例，cur 为根节点 4 时，其左子树的最右节点为 3，此时将 3 的右指针指向当前节点 4，然后 cur 向左移动，进入其左子树。此后 cur 移动到节点 3 时，其右指针已经指向 4，然后当 cur 向右移动时，会回到 4，按照规则，需要继续找 4 的左子树的最右节点，此时右找到了 3，然后发现其右指针不是空，而是指向 cur 也就是 4，此时说明 4 的左子树已经遍历完，向右移动到 6。然后继续。

按照这个规则，得到遍历序列，称为 Morris 序：

可以看到在二叉树的 Morris 序中，对于没有左子树的节点只会到达 1 次，这一次到达后，cur 的下一步均走向 cur -> right，如果 cur 有右子树，则 cur -> right 为其右子树，如果 cur 没有右子树，cur -> right 为指向 cur 的 Morris 后继的线索。

对于能够到达两次的节点，第一次到达时，cur 均会走向 cur -> left，将左子树遍历一圈后，会第二次倒到 cur，接下来 cur 下一步走向 cur -> right，同样地，如果 cur 有右子树，则 cur -> right 为其右子树，如果 cur 没有右子树，cur -> right 为指向 cur 的 Morris 后继的线索。

对于有左子树的节点 cur，通过 precursor -> right 判断是第一次还是第二次到达，若为 precursor -> right = nullptr 则为第一次到达，若 precursor -> right = cur 则为第二次到达。

代码 (C++，模板)

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
vector<int> morrisTraversal(TreeNode* root)
{
    if(!root)
        return {};
    TreeNode *cur = root;
    vector<int> result;
    while(cur)
    {
        result.push_back(cur -> val);
        if(cur -> left)
        {
            // cur 有左子树
            TreeNode *precursor = cur -> left;
            while(precursor -> right && precursor -> right != cur)
                precursor = precursor -> right;
            if(!precursor -> right)
            {
                // 第一次到达 cur
                precursor -> right = cur; // 连接线索
                cur = cur -> left;
            }
            else
            {
                // 第二次到达 cur
                precursor -> right = nullptr; // 断开线索
                cur = cur -> right;
            }
        }
        else
            cur = cur -> right;
    }
    return result;
}

测试

还是用前面的例图来测试，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(){}
    TreeNode(int val):val(val),left(nullptr),right(nullptr){}
};

int main()
{
    TreeNode *root = new TreeNode(4);
    root -> left = new TreeNode(2);
    root -> right = new TreeNode(6);
    root -> left -> left = new TreeNode(1);
    root -> left -> right = new TreeNode(3);
    root -> right -> left = new TreeNode(5);
    root -> right -> right = new TreeNode(7);

    vector<int> result = morrisTraversal(root);
    for(int x: result)
        cout << x << " ";
    cout << endl;
}

结果如下，与前面推导的 Morris 序列相同。

Morris 遍历算法分析

Morris 遍历过程中，只用了几个变量，额外空间复杂度为 $O(1)$。

每到一个有左子树的节点，都要找一遍左子树的最右节点。所有节点走一遍找左子树的最右节点涉及的总结点个数为 $O(N)$，涉及到的节点都会走两次，因此找左子树的最右节点的总时间复杂度为 $O(N)$，于是 Morris 遍历的时间复杂度为 $O(N)$。

Morris 前序遍历

由 Morris 遍历和 Morris 序：

对于 cur 只能到达一次的节点，cur 到达时直接访问。

对于 cur 到达两次的节点，cur 第 1 次到达时访问。

代码 (C++)

与 Morris 代码模板相比，仅 result.push_back(cur -> val) 的位置有变化。

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
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        TreeNode *cur = root;
        vector<int> result;
        while(cur)
        {
            if(cur -> left)
            {
                // cur 有左子树
                TreeNode *precursor = cur -> left;
                while(precursor -> right && precursor -> right != cur)
                    precursor = precursor -> right;
                if(!precursor -> right)
                {
                    // 第一次到达 cur
                    result.push_back(cur -> val);
                    precursor -> right = cur; // 连接线索
                    cur = cur -> left;
                }
                else
                {
                    // 第二次到达 cur
                    precursor -> right = nullptr; // 断开线索
                    cur = cur -> right;
                }
            }
            else
            {
                result.push_back(cur -> val);
                cur = cur -> right;
            }
        }
        return result;
    }
};

Morris 中序遍历

由 Morris 遍历和 Morris 序：

对于 cur 只能到达一次的节点，cur 到达时直接访问。

对于 cur 到达两次的节点，cur 第 2 次到达时才访问。

代码 (C++)

与 Morris 代码模板相比，仅 result.push_back(cur -> val) 的位置有变化。

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
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        TreeNode *cur = root;
        vector<int> result;
        while(cur)
        {
            if(cur -> left)
            {
                // cur 有左子树
                TreeNode *precursor = cur -> left;
                while(precursor -> right && precursor -> right != cur)
                    precursor = precursor -> right;
                if(!precursor -> right)
                {
                    // 第一次到达 cur
                    precursor -> right = cur; // 连接线索
                    cur = cur -> left;
                }
                else
                {
                    // 第二次到达 cur
                    result.push_back(cur -> val);
                    precursor -> right = nullptr; // 断开线索
                    cur = cur -> right;
                }
            }
            else
            {
                result.push_back(cur -> val);
                cur = cur -> right;
            }
        }
        return result;
    }
};

Morris 后序遍历

由 Morris 遍历和 Morris 序：

对于 cur 只能到达一次的节点，cur 到达时直接跳过，不访问。

对于 cur 到达两次的节点，cur 第 2 次到达时，逆序访问其左子树的右边界。

Morris 遍历完成后，逆序访问整棵树的右边界。

代码 (C++)

访问 cur 节点的右边界，封装在函数 _right_list_reverse_result(cur) 中，过程是先将右边界这条链表反转，然后按链表顺序访问，然后再将这条链表翻转，相当于还原。

逆序访问，涉及到一个翻转链表的过程，封装在函数 _reverseTreeRightList(cur) 中。

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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        TreeNode *cur = root;
        vector<int> result;
        while(cur)
        {
            if(cur -> left)
            {
                // cur 有左子树
                TreeNode *precursor = cur -> left;
                while(precursor -> right && precursor -> right != cur)
                    precursor = precursor -> right;
                if(!precursor -> right)
                {
                    // 第一次到达 cur
                    precursor -> right = cur; // 连接线索
                    cur = cur -> left;
                }
                else
                {
                    // 第二次到达 cur
                    precursor -> right = nullptr; // 断开线索
                    _right_list_reverse_result(cur -> left, result);
                    cur = cur -> right;
                }
            }
            else
            {
                cur = cur -> right;
            }
        }
        _right_list_reverse_result(root, result);
        return result;
    }

private:
    void _right_list_reverse_result(TreeNode* root, vector<int>& result)
    {
        TreeNode *tmp = _reverseTreeRightList(root);
        TreeNode *iter = tmp;
        while(iter)
        {
            result.push_back(iter -> val);
            iter = iter -> right;
        }
        root = _reverseTreeRightList(tmp);
    }

    TreeNode* _reverseTreeRightList(TreeNode* head) {
        // 空链表
        if(head == nullptr) 
            return head;
        // 只有一个元素的链表
        if(head -> right == nullptr) 
            return head;

        // 至少两个元素，prev初始为第一个，iter初始为第二个
        TreeNode *prev = head;
        TreeNode *iter = head -> right;
        TreeNode *tmp = nullptr;

        while(iter -> right != nullptr)
        {
            tmp = iter -> right;
            iter -> right = prev;
            prev = iter;
            iter = tmp;
        }

        iter -> right = prev;
        head -> right = nullptr;
        head = iter;

        return head;
    }
};

题目

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

1
2
树上节点的数目在范围 [2, 1000] 内
-2^31 <= Node.val <= 2^31 - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

算法1：中序遍历

由于恰好有两个节点错误地交换了，记这两个节点分别为 result[0] 和 result[1]。

最直接的做法是将中序遍历序列返回回来，该序列与升序序列相比，有两个位置不一样，将这两个位置对应的节点 swap 一下即可。

返回中序遍历序列需要 $O(N)$ 额外空间，因此需要在中序遍历的过程中记录 result 的两个值。这需要在中序遍历过程中，对比 node 及其中序前驱 precursor。

参考 中序遍历过程中通过引用维护前驱 中的做法维护前驱。

设 result[0] 是错误交换的节点对中，在中序遍历中靠前的那一个。也就是对 reuslt[0] 和 reuslt[1] 这两个节点来说，由于 result[0] 的中序遍历靠前，因此本来应该更小，但由于错误交换，result[1] 成了更小的那个。因此在中序遍历过程中：

  • 第一次发现 precursor -> val > node -> val 时，precursor 就是因为错误交换而使其值变大，导致了 precursor -> val >= node -> val。记 result[0] = precursor。

  • 第二次发现 precursor -> val > node -> val 时，node 就是因为错误额交换而使其值变小，导致了 precursor -> val > node -> val，记 result[1] = node。

代码 C(++)

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
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *precursor = nullptr;
        PTT result(nullptr, nullptr);
        _inOrder(root, precursor, result, false);
        swap(result.first -> val, result.second -> val);
    }

private:
    using PTT = pair<TreeNode*, TreeNode*>;

    void _inOrder(TreeNode* node, TreeNode*& precursor, PTT& result, bool flag)
    {
        // 每次递归只对比 node 及其中序前驱
        if(flag) 
            return;

        if(node -> left)
            _inOrder(node -> left, precursor, result, flag);

        if(precursor && precursor -> val >= node -> val)
        {
            result.second = node;
            if(!result.first)
            {
                // 第一次遇到
                result.first = precursor;
            }
            else 
            {
                // 第二次遇到
                flag = true;
                return;
            }
        }

        precursor = node;

        if(node -> right)
            _inOrder(node -> right, precursor, result, flag);
    }
};

算法2：Morris 中序遍历

将中序遍历改为 Morris，其余逻辑一样。

由于 Morris 遍历涉及到连接和断开线索，因此遍历必须走完，找到了两个目标节点也不能提前退出。

代码 (C++)

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
class Solution {
public:
    void recoverTree(TreeNode* root) {
        using PTT = pair<TreeNode*, TreeNode*>;
        PTT result(nullptr, nullptr);
        TreeNode *precursor = nullptr;
        TreeNode *cur = root;
        while(cur)
        {
            if(cur -> left)
            {
                // cur 有左子树
                TreeNode *tmp = cur -> left;
                while(tmp -> right && tmp -> right != cur)
                    tmp = tmp -> right;
                if(!tmp -> right)
                {
                    // 第一次到达 cur
                    tmp -> right = cur; // 连接线索
                    cur = cur -> left;
                }
                else
                {
                    // 第二次到达 cur，则中序遍历当前节点为 cur
                    precursor = tmp;
                    if(precursor && precursor -> val >= cur -> val)
                    {
                        result.second = cur;
                        if(!result.first)
                        {
                            // 第一次遇到
                            result.first = precursor;
                        }
                    }
                    tmp -> right = nullptr; // 断开线索
                    precursor = cur;
                    cur = cur -> right;
                }
            }
            else
            {
                if(precursor && precursor -> val >= cur -> val)
                {
                    result.second = cur;
                    if(!result.first)
                    {
                        // 第一次遇到
                        result.first = precursor;
                    }
                }
                precursor = cur;
                cur = cur -> right;
            }
        }

        swap(result.first -> val, result.second -> val);
    }
};

morris

Share