Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

Morris遍历:

优点:不同于我们之前递归遍历或者借助栈来进行树的遍历,因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)

假设当前节点为cur,最一开始来到树根,什么时候停呢,当cur来到nil的时候就停止

  1. 如果当前节点没有左子树,直接向右移动
  2. 如果当前节点有左子树,找到当前节点左子树的最右节点mostRight
    1. 如果mostRight的右指针指向null,那么mostRight.Right=Cur,cur=cur.Left
    2. 如果mostRight的右指针指向cur,那么mostRight.Right=nil,cur=cur.Right

遍历之后发现一个问题:任何一个节点,只要有左孩子Morris遍历的时候会遍历两次,也就是有左树的节点,左树不为空,首先遍历当前节点,然后遍历左树,遍历之后再回到当前节点,所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。

Morris先序遍历:

第一次遍历到该节点的时候直接打印(没有左子树的节点会遍历到一次,有左子树的节点会遍历到两次,但是我们第一次就应该打印)

Morris先序遍历代码
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
func MorrisPreOrderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var mostRight *TreeNode
cur := root
var ret []int
for cur != nil {
//如果当前节点没有左子树
if cur.Left == nil { //当前节点向右移动 (只有没有左子树的节点会走这一步)
ret = append(ret, cur.Val)
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left

for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
ret = append(ret, cur.Val)
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}

return ret
}