二叉树morris遍历

神级算法

Posted by liuwenzi on May 11, 2020
阅读数:

无意间发现了一种神级算法,遍历二叉树只需要O(1)的空间复杂度。

morris算法

我们对二叉树的遍历无非两种

  • 广度优先(利用队列进行层次遍历) 空间复杂度O(n)
  • 深度优先(递归)log(n)

那么morris是如何做到O(1)空间复杂度的呢?

morris利用叶子节点来记录父节点,它把左孩子的最右孩子指向父节点,以此循环。它跟广度优先和深度优先的最根本区别就是morris算法不用花费空间记录父节点,它把左孩子的最右节点的右孩子指向父节点。文字描述起来有点绕。看图

①、当我们访问1节点的左孩子,进入3节点,找到3节点的最右孩子,并将3的最右孩子(即6节点)的右孩子指向1节点

②、然后继续访问5节点,将5节点的最右孩子(即5节点的右孩子)指向3节点。

③、继续访问5节点的左孩子,发现左孩子为空,访问5节点的左孩子,此时5节点的左孩子指向3节点

④、继续访问3节点的左孩子(即5节点),发现5节点的最右孩子指向3节点,此时将5节点的最右孩子的孩子指向null

⑤、继续访问3节点的右孩子(即6节点),发现6节点没有左孩子,此时进入6节点的右孩子(即1节点),寻找1节点的左孩子的最右孩子(即6节点),发现已经指向1节点,此时将6节点的右孩子指向null

⑥、继续访问1节点的右孩子(即节点2)接下来跟前面一样,就不赘述了。

大概的思路就是这样子,看看代码如何实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @author mosquito
 * @version 1.0
 * @description
 * @date 2020/5/11 - 11:29 上午
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Morris {
    private TreeNode treeNode;
    public void morris(TreeNode root){
        while(root!=null){
            if(root.left == null){
                System.out.println(root.val);
                root = root.right;
            }else{
                TreeNode prev = getPredecessor(root);
                if(prev.right == null){
                    //如果左孩子的最右孩子的右孩子指向null,则将其指向父节点
                    prev.right = root;
                    System.out.println(root.val);
                    root = root.left;
                }else{
                    //若指向父节点,则断掉指针,恢复形状
                    prev.right = null;
                    root = root.right;
                }
            }
        }
    }
    //找到左孩子的最右孩子
    public TreeNode getPredecessor(TreeNode root){
        TreeNode predecessor = root;
        predecessor = predecessor.left;
        while(predecessor.right != null && predecessor.right != root){
            predecessor = predecessor.right;
        }
        return predecessor;
    }
}

这样就ok啦!