图解二叉树的Morris(莫里斯)遍历

发布时间:2023年12月29日

二叉树的Morris(莫里斯)遍历

本文参考链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/490846864/

Morris 遍历使用二叉树节点中大量指向 null 的指针,时间复杂度:O(n),额外空间复杂度:O(1)。

Morris 的整体思路就是将 以某个根结点开始,找到它左子树的最右侧节点之后与这个根结点进行连接。

在这里插入图片描述

我们可以从图中看到,连接之后,指针是可以完整的从根节点顺着下一个节点遍历,将整棵树遍历完毕,直到 7 这个节点右侧没有指向。

模板代码

首先介绍morris的模板代码,带*的注释表示该行为指定遍历所要增加的内容,可以先不管。

模板代码的流程图如下所示:

在这里插入图片描述

在这里插入图片描述

public List<Integer> traversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    //1.定义cur和prev
    TreeNode cur = root;
    TreeNode prev = null;

    //2.当cur不为空时
    while (cur != null) {
        //2.1prev为cur左子树
        prev = cur.left;

        //2.2prev不为空时
        if (prev != null) {
            //2.2.1用prev找到左子树最右侧节点
            while (prev.right != null && prev.right != cur) {
                prev = prev.right;
            }

            //2.2.2prev右子树不为空时,连接
            if (prev.right == null) {
                prev.right = cur;
                //*前+res.add(cur.val);
                cur = cur.left;
            } else { //2.2.3prev右子树不为空时,断开连接
                prev.right = null;
                //*中+res.add(cur.val); *后+print(cur.left)
                cur = cur.right;
            }
        } else { //2.3prev为空时
            //*前中+res.add(cur.val);
            cur = cur.right;
        }
    }
    //*后+print(root)
    return res;
}

前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    //1.定义cur和prev
    TreeNode cur = root;
    TreeNode prev = null;

    //2.当cur不为空时
    while (cur != null) {
        //2.1prev为cur左子树
        prev = cur.left;

        //2.2prev不为空时
        if (prev != null) {
            //2.2.1用prev找到左子树最右侧节点
            while (prev.right != null && prev.right != cur) {
                prev = prev.right;
            }

            //2.2.2prev右子树不为空时,连接
            if (prev.right == null) {
                prev.right = cur;
                res.add(cur.val);
                cur = cur.left;
            } else { //2.2.3prev右子树不为空时,断开连接
                prev.right = null;
                cur = cur.right;
            }
        } else { //2.3prev为空时
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    //1.定义cur和prev
    TreeNode cur = root;
    TreeNode prev = null;

    //2.当cur不为空时
    while (cur != null) {
        //2.1prev为cur左子树
        prev = cur.left;

        //2.2prev不为空时
        if (prev != null) {
            //2.2.1用prev找到左子树最右侧节点
            while (prev.right != null && prev.right != cur) {
                prev = prev.right;
            }

            //2.2.2prev右子树不为空时,连接
            if (prev.right == null) {
                prev.right = cur;
                cur = cur.left;
            } else { //2.2.3prev右子树不为空时,断开连接
                prev.right = null;
                res.add(cur.val);
                cur = cur.right;
            }
        } else { //2.3prev为空时
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

后序遍历

当连接已完成时,断开连接后,打印下层的单链表,比如返回到2时,打印4,返回到1时,打印5,2,涉及到了逆序打印单链表的内容。注意应该是打印下一层,而不是当前层。循环结束后打印根节点所在的一侧,即7,3,1。

在这里插入图片描述

List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {

    if (root == null) {
        return res;
    }

    //1.定义cur和prev
    TreeNode cur = root;
    TreeNode prev = null;

    //2.当cur不为空时
    while (cur != null) {
        //2.1prev为cur左子树
        prev = cur.left;

        //2.2prev不为空时
        if (prev != null) {
            //2.2.1用prev找到左子树最右侧节点
            while (prev.right != null && prev.right != cur) {
                prev = prev.right;
            }

            //2.2.2prev右子树不为空时,连接
            if (prev.right == null) {
                prev.right = cur;
                cur = cur.left;
            } else { //2.2.3prev右子树不为空时,断开连接
                prev.right = null;
                print(cur.left); //打印左子树
                cur = cur.right;
            }
        } else { //2.3prev为空时
            cur = cur.right;
        }
    }
    print(root); //打印根节点所在一侧
    return res;
}

//打印链表
public void print(TreeNode head) {
    TreeNode revList = reverseList(head);
    TreeNode cur = revList;
    while (cur != null) {
        res.add(cur.val);
        cur = cur.right;
    }
    reverseList(revList);
}

//翻转单链表
public TreeNode reverseList(TreeNode head) {
    TreeNode cur = head;
    TreeNode prev = null;

    while (cur != null) {
        TreeNode next = cur.right;
        cur.right = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

文章来源:https://blog.csdn.net/weixin_43217281/article/details/135189764
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。