Martisss's blog

hello, world

0%

morris中序遍历

发表于 分类于

Morris遍历

介绍

morris遍历是利用二叉树本身空闲出来的指针(n个节点的二叉树有n+1个指针空闲)来作为辅助变量完成二叉树的遍历的一种方法。Morris遍历法能以O(1)的空间复杂度和O(n)的时间复杂度实现二叉树的三种遍历,其中不使用栈或额外空间。

Morris中序遍历过程

记当前节点为root, 设置一个predecessor指针用来指向当前节点左子树的最右边节点（中序遍历的前驱节点）

  1. 如果root无左孩子，root向右移动

  2. 如果root有左孩子，predecessor指向root左子树的最右边节点

    1. 如果predecessor的right指针指向空，让其指向root，root向左移动
    2. 如果predecessor的right指针指向root，让其指向null，root向右移动
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
var inorderTraversal = function(root) {
    let res = []
    let cur = root
    let mosRight = null
    while(cur !== null) {
        //有左子树，找前驱节点，判断是第一次访问还是第二次访问
        if(cur.left !== null) {
            mosRight = cur.left
            while(mosRight.right !== null && mosRight.right !== cur) {
                mosRight = mosRight.right
            } 
            //是第一次访问，访问左子树//是第一次访问，访问左子树
            if(mosRight.right === null) {
                mosRight.right = cur
                cur = cur.left
            } else {  
                //第二次访问了，那么应当消除链接
                //该节点访问完了，接下来应该访问其右子树
                mosRight.right = null
                res.push(cur.val)
                cur = cur.right
            }
        } else { //没有左子树，直接访问该节点，再访问右子树
            res.push(cur.val)
            cur = cur.right
        }
    }
    return res
}

前序遍历

后序遍历

复杂度分析

对于二叉树来说，传统的遍历方式，一个节点最多只可能被访问两次，因此其时间复杂度均为O(n)。而由于借助了栈和队列这样的辅助数据结构，无论哪种方式，其空间复杂度与树高有直接关系，因此传统遍历方式空间复杂度为平均O(logn)，最差O(n)

而morris遍历对于每一个有左子树的节点，其寻找前驱的过程只会执行两次，一次是建立前驱-后继关系的时候，一次是恢复树结构的时候。因此事实上，二叉树的每条路最多只可能被循环访问两次，其时间复杂度必然为O(n)，空间复杂度O（1）

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

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
var recoverTree = function(root) {
    let x = null, y = null, pred = null, predecessor = null
    while(root !== null) {
        if(root.left !== null) {
            // 首先让predecessor指针指向root.left,然后一直向右走到尽头
            predecessor = root.left
            while(predecessor.right !== null && predecessor.right !== root) {
                predecessor = predecessor.right
            }
            // 走到root节点左子树的最右边节点后，将其右指针指向root,然后将root指针指向其左节点，开始新一轮遍历
            if(predecessor.right === null) {
                predecessor.right = root
                root = root.left
            } 
            // predecessor指针不为空，说明左子树已经访问完了，需要断开连接，也就是对子树进行恢复，不然就成为了一个图
            else {
                if(pred !== null && root.val < pred.val) {
                    y = root
                    if(x === null) {
                        x = pred
                    }
                }
                pred = root
                predecessor.right = null
                // 左边找完了，找右边
                root = root.right
            }
        }
        else {
            // 如果没有左孩子，则访问右孩子
            if(pred !== null && root.val < pred.val) {
                y = root
                if(x === null) {
                    x = pred
                }
            }
            pred = root
            root = root.right
        }
    }
    [x.val, y.val] = [y.val, x.val]
}