Morris算法


Morris遍历

Morris遍历方法

记作当前节点为cur。

  1. 如果cur无左孩子,cur向右移动(cur=cur.right)
  2. 如果cur有左孩子,找到cur左子树上最右的节点,记为mostright
    1. 如果mostright的right指针指向空,让其指向cur,cur向左移动(cur=cur.left)
    2. 如果mostright的right指针指向cur,让其指向空,cur向右移动(cur=cur.right)

实现以上的原则,即实现了morris遍历。

时间复杂度为$O(n)$,空间复杂度为$O(1)$。

Morris中序遍历

Morris中序遍历即在Morris遍历的基础上,当满足条件1和条件2.2时,输出当前结点即可。

  1. 如果cur无左孩子,输出当前结点,cur向右移动(cur=cur.right)

  2. 如果cur有左孩子,找到cur左子树上最右的节点,记为mostright

    1. 如果mostright的right指针指向空,让其指向cur,cur向左移动(cur=cur.left)
    2. 如果mostright的right指针指向cur,让其指向空,输出当前结点,cur向右移动(cur=cur.right)

    重复以上步骤直到当前结点为空

代码实现

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    //注意此处predecessor->right != root条件限制!!!
                    predecessor = predecessor->right;
                }

                // 让 predecessor 的右指针指向 root,继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了,我们需要断开链接
                else {
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子,则直接访问右孩子
            else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

Morris前序遍历

  1. 如果cur无左孩子,输出当前结点,cur向右移动(cur=cur.right)
  2. 如果cur有左孩子,找到cur左子树上最右的节点,记为mostright

    1. 如果mostright的right指针指向空,让其指向cur,输出当前结点,cur向左移动(cur=cur.left)
    2. 如果mostright的right指针指向cur,让其指向空,cur向右移动(cur=cur.right)

    重复以上步骤直到当前结点为空

class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
        vector res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    res.emplace_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                }
            } else {
                res.emplace_back(p1->val);
            }
            p1 = p1->right;
        }
        return res;
    }
};

Morris后序遍历

这个太tm复杂了

  • 新建临时节点,令该节点为 root;

  • 如果当前节点的左子节点为空,则遍历当前节点的右子节点;

  • 如果当前节点的左子节点不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点;

    1. 如果前驱节点的右子节点为空,将前驱节点的右子节点设置为当前节点,当前节点更新为当前节点的左子节点。

    2. 如果前驱节点的右子节点为当前节点,将它的右子节点重新设为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点。

  • 重复步骤 2 和步骤 3,直到遍历结束。

class Solution {
public:
    void addPath(vector &vec, TreeNode *node) {
        int count = 0;
        while (node != nullptr) {
            ++count;
            vec.emplace_back(node->val);
            node = node->right;
        }
        reverse(vec.end() - count, vec.end());
    }

    vector postorderTraversal(TreeNode *root) {
        vector res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                    addPath(res, p1->left);
                }
            }
            p1 = p1->right;
        }
        addPath(res, root);
        return res;
    }
};

后续

在本博客所有代码运行情况下,Morris算法并不能比递归减少较多的内存占用


文章作者: zzx
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 zzx !
评论
  目录