Java 二叉树遍历特别篇之 Morris 遍历

简介

Morris 遍历是一种基于线索二叉树的遍历方式，它利用了二叉树中大量的空指针，将遍历的信息存储在空指针中，从而省去了递归和栈的空间消耗。这种遍历方式的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，因此比递归和栈的遍历方式更加高效。

本文将对 Morris 遍历进行详细的讲解，并提供两条示例说明。

Morris 遍历流程

中序遍历

中序遍历是 Morris 遍历的核心，利用 Morris 遍历进行中序遍历的具体步骤如下：

1. 初始化当前节点为根节点。
2. 如果当前节点的左子节点为空，则输出该节点的值，并将当前节点更新为其右子节点。
3. 如果当前节点的左子节点不为空，找到当前节点的左子树中的最右节点，即是节点的前驱，这个前驱节点没有右子节点或右子节点为当前节点。
4. 如果前驱节点的右子节点为空，则将前驱节点的右子节点指向当前节点，并将当前节点更新为其左子节点。
5. 如果前驱节点的右子节点为当前节点，则将前驱节点的右子节点清空（恢复着节点原有的结构），输出该节点的值，并将当前节点更新为其右子节点。

示例代码：

public void morrisInorder(TreeNode root){
    TreeNode cur = root;
    while(cur != null){
        if(cur.left == null){
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        else{
            // 找到当前节点的前驱
            TreeNode pre = cur.left;
            while(pre.right != null && pre.right != cur){
                pre = pre.right;
            }
            if(pre.right == null){
                // 建立线索
                pre.right = cur;
                cur = cur.left;
            }
            else{
                // 恢复着节点原有的结构
                pre.right = null;
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }
}

前序遍历

利用 Morris 遍历进行前序遍历的具体步骤如下：

1. 初始化当前节点为根节点。
2. 如果当前节点的左子节点为空，则输出该节点的值，并将当前节点更新为其右子节点。
3. 如果当前节点的左子节点不为空，找到当前节点的左子树中的最右节点，即是节点的前驱，这个前驱节点没有右子节点或右子节点为当前节点。
4. 如果前驱节点的右子节点为空，则将前驱节点的右子节点指向当前节点，并输出该节点的值，将当前节点更新为其左子节点。
5. 如果前驱节点的右子节点为当前节点，则将前驱节点的右子节点清空（恢复着节点原有的结构），并将当前节点更新为其右子节点。

示例代码：

public void morrisPreorder(TreeNode root){
    TreeNode cur = root;
    while(cur != null){
        if(cur.left == null){
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        else{
            // 找到当前节点的前驱
            TreeNode pre = cur.left;
            while(pre.right != null && pre.right != cur){
                pre = pre.right;
            }
            if(pre.right == null){
                // 建立线索
                pre.right = cur;
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            else{
                // 恢复着节点原有的结构
                pre.right = null;
                cur = cur.right;
            }
        }
    }
}

Morris 遍历优点和缺点

Morris 遍历的时间复杂度和空间复杂度都非常优秀，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，比递归和栈的遍历方式更加高效。

但是，Morris 遍历对于二叉树的结构有一定限制，只适用于没有左子树或无法返回右子节点的节点，否则就会出现回环，导致死循环。因此，Morris 遍历并不是遍历二叉树的通用解决方案。

总结

Morris 遍历是一种基于线索二叉树的遍历方式，可以实现 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度的遍历，优于递归和栈的遍历方式。本文讲解了 Morris 遍历的具体步骤，并提供了中序遍历和前序遍历的示例代码。同时，对 Morris 遍历的优点和缺点进行了简要讨论，希望本文对大家有所启发。