二叉树的Morris遍历

前言

前面已经进行过二叉树的递归遍历和迭代遍历，在前两种遍历中，二叉树遍历的空间复杂度都是O(n)，这是因为不管是递归遍历还是迭代遍历，都用了栈空间来帮我们维护调用关系，方便我们在走到端点的时候可以回退。

那么，换一个思路想想，我们可不可以不用栈，而是通过记录下节点要回退的位置，帮助我们直接退回到目标节点呢？这个回退的指针我们又该怎么维护呢？可以发现，二叉树的叶子节点的左右指针都为空，而我们需要回退的位置也是在叶子节点触发，那么我们考虑可以将叶子节点的指针指向目标节点，这样也就不需要额外的栈空间了。

而事实上，Morris遍历之所以能将二叉树的空间复杂度降为O(1)，也是这么做的。

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）

以上就是Morris遍历的规则，其中mostright的节点，即为节点在中序遍历中的前序节点。
Morris遍历的本质就是会遍历两次节点，一个快指针，一个慢指针，慢指针到达一个节点的时候，快指针就走到当前节点的左子树的最右节点，将该节点的右指针指向慢指针的位置，然后慢指针再移动到下一步。如此往复，等回退的时候，就可以通过之前便利过程中建立的指针关系迅速回到目标节点位置。

Morris前序遍历
接下来，先看一下Morris前序遍历的实现。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        // 慢指针
        TreeNode cur = root;
        // 快指针,寻找cur的中序遍历的前序节点
        TreeNode mostright = null;
        
        while (cur != null) {
            // 快指针移动到左子树
            mostright = cur.left;
            
            if (mostright != null) {
                // 左子树不为空,快指针移动到左子树的最右节点,即cur的中序遍历的前序节点
                // 此处注意不能走过头,如果最右节点已经标记过,就停在最右节点处
                while (mostright.right != null && mostright.right != cur) {
                    mostright = mostright.right;
                }
                
                if (mostright.right == null) {
                    // 如果是最右节点还没有和当前节点建立关系,就建立关系,
                    // 因为是前序遍历,cur指针在移动之前都要记录
                    res.add(cur.val);
                    mostright.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 逻辑到这里,说明本次遍历到的最右节点已经和当前节点建立了关系,本次是第二次遍历到cur所在的节点,所以把关系清除.
                    mostright.right = null;
                }
            } else {
                // 此时的mostright在左节点,如果左节点为空,cur不用向左走了,直接记录下来
                res.add(cur.val);
            }
            // 到这里两种情况,左子树为空,且当前节点已经记录,往右走
            // cur指针到达了某个节点的左子树的最右节点,回到那个节点
            cur = cur.right;
        }
        return res;

    }

Morris中序遍历

在前序遍历的基础上，中序遍历需要改动一下记录cur节点的触发时机

public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root == null) {
                return res;
            }
            // 慢指针
            TreeNode cur = root;
            // 快指针,寻找cur的中序遍历的前序节点
            TreeNode mostright = null;

            while (cur != null) {
                // 快指针移动到左子树
                mostright = cur.left;

                if (mostright != null) {
                    // 左子树不为空,快指针移动到左子树的最右节点,即cur的中序遍历的前序节点
                    // 此处注意不能走过头,如果最右节点已经标记过,就停在最右节点处
                    while (mostright.right != null && mostright.right != cur) {
                        mostright = mostright.right;
                    }

                    if (mostright.right == null) {
                        // 如果是最右节点还没有和当前节点建立关系,就建立关系,
                        mostright.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                        // 中序遍历,左子树遍历完成,记录当前节点
                        res.add(cur.val);
                        // 逻辑到这里,说明本次遍历到的最右节点已经和当前节点建立了关系,本次是第二次遍历到cur所在的节点,左子树已经遍历完成,所以把关系清除.
                        mostright.right = null;
                    }
                } else {
                    // 此时的mostright在左节点,如果左节点为空,cur不用向左走了,直接记录下来
                    res.add(cur.val);
                }
                // 到这里两种情况,左子树为空,且当前节点已经记录,往右走
                // cur指针到达了某个节点的左子树的最右节点,回到那个节点
                cur = cur.right;
            }
            return res;
    }