莫里斯算法

莫里斯算法遍历二叉树

Posted by Jae on May 9, 2019

1、二叉树的遍历

对于二叉树的遍历分为三种:前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。假设一个树高为h的二叉树,三种遍历算法的时间复杂度都是O(n),空间复杂度为O(h) 因为遍历二叉树的每一个节点,最好的情况就是每一个节点被访问一次,所以时间复杂度无法再优化,但是空间复杂度仍然可以优化。 二叉树的遍历算法可以使用递归和非递归来实现,递归会有隐式的调用堆栈,非递归使用额外的数据结构来支持。

哪如何在遍历过程中避免去申请额外的空间呢?我们知道对于一个拥有n个节点的二叉树,有2n个指针域,但是非空指针域有n-1个,空指针域有n+1个,这些空指针域能不能拿来用呢? 线索二叉树就是首先对一棵二叉树变成一棵线索二叉树,线索二叉树就是将左孩子空指针域指向其前驱节点,右孩子空指针域指向其后继节点,莫里斯算法就是基于线索二叉树来实现O(1)空间复杂度的遍历。

2、莫里斯算法思想

我们有下面的二叉树: 二叉树 如果采用中序遍历,顺序为: 1,2,3,4,5,6,7,8,9,10

2.1 线索二叉树

我们首先将该二叉树变成线索二叉树如下: 线索二叉树 可以看到对于节点的空指针域用来指向其前驱和后继节点,这样就将闲置的空间利用起来了,而不用堆栈保存上一层节点的位置,节省了空间。

2.2 前序节点

如何寻找前序节点? 如果当前节点有左孩子,那么从左孩子开始一直沿着右孩子指针一直往右走,直到走到叶子节点为止,该叶子节点即为当前节点的前序节点,例如节点6,首先移动到左孩子4,然后从该节点的右孩子移动到叶子节点5,5即是节点6的前序节点。

2.3 莫里斯中序遍历

根据当前节点,找到其前序节点,如果该前序节点右孩子为空,咋将前序节点的右孩子指向当前节点,然后进入当前节点的左孩子;

如果当前节点的左孩子为空,访问该节点,然后进入其右孩子;

如果当前节点的前序节点的右孩子指向自身,将前序节点的右孩子设置为null,访问该节点,然后进入其右孩子。

3、实现

// 获取前序节点
public TreeNode getPredecessor(TreeNode root){
    TreeNode pre = root;
    if (root.left != null){
        pre = pre.left;
        // 一直往右孩子移动
        while (pre.right != null && pre.right != root){
            pre = pre.right;
        }
    }

    return pre;
}

// 莫里斯中序遍历
public void morrisTravel(TreeNode root){
    while (root != null){
        if(root.left == null){
            // 打印当前节点
            System.out.println(root.val);
            // 进入到右孩子
            root = root.right;
        }else {
            // 找到当前节点的前序节点
            TreeNode pre = getPredecessor(root);
            // 如果前序节点的右孩子为null,将右孩子指向当前节点
            if (pre.right == null){
                pre.right = root;
                root = root.left;
            }else if (pre.right == root){
                pre.right = null;
                System.out.println(root.val);
                root = root.right;
            }
        }
    }
}