二叉树的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;
}