二叉树的Morris前中后序遍历
水水
新年好捏🎆
24年的大年初一，终于更一下年前就打算弄的一个文章。
在力扣做hot100的时候，做到树的章节，开头就是二叉树的中序遍历实现，嘿，递归和正常非递归实现都好说，但是有个Morris方法，把空间复杂度降到O(1)，刚好很久之前做这题的时候也是一知半解，仔细一看和线索二叉树有关，所以打算好好看看
先说说递归和一般非递归(迭代)遍历实现
这俩本质上不差多少，都是用栈实现，只是一个是系统栈，一个是自定义的栈
先把树节点结构定义一下，基于Go书写，且定位为LeetCode原题:
二叉树前序遍历
二叉树中序遍历
二叉树后序遍历
1
2
3
4
5
6
7
8
| type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
|
递归实现
时间复杂度是O(n)，空间复杂度是O(n)，使用系统栈
很好理解嘛，到达当前节点后，直接去到左右子节点，一直到叶子节点，再逐层调用返回
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
| func preorderTraversal(root *TreeNode) (vals []int) {
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
vals = append(vals, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
| func inorderTraversal(root *TreeNode) (res []int) {
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
res = append(res, node.Val)
inorder(node.Right)
}
inorder(root)
return
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
| func postorderTraversal(root *TreeNode) (res []int) {
var postorder func(*TreeNode)
postorder = func(node *TreeNode) {
if node == nil {
return
}
postorder(node.Left)
postorder(node.Right)
res = append(res, node.Val)
}
postorder(root)
return
}
|
非递归(迭代)实现
时间复杂度是O(n)，空间复杂度是O(n)，使用自定义栈
和递归一样，只是自己手动去控制栈，直接深入到叶子节点，然后再自底向上去走节点，逐层遍历完
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func preorderTraversal(root *TreeNode) (vals []int) {
stack := []*TreeNode{}
node := root
for node != nil || len(stack) > 0 {
for node != nil {
vals = append(vals, node.Val)
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1].Right
stack = stack[:len(stack)-1]
}
return
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func inorderTraversal(root *TreeNode) (res []int) {
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func postorderTraversal(root *TreeNode) (res []int) {
stk := []*TreeNode{}
var prev *TreeNode
for root != nil || len(stk) > 0 {
for root != nil {
stk = append(stk, root)
root = root.Left
}
root = stk[len(stk)-1]
stk = stk[:len(stk)-1]
if root.Right == nil || root.Right == prev {
res = append(res, root.Val)
prev = root
root = nil
} else {
stk = append(stk, root)
root = root.Right
}
}
return
}
|
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
| func preorderTraversal(root *TreeNode) (res []int) {
for root != nil {
if root.Left != nil {
processor := root.Left
for processor.Right != nil && processor.Right != root {
processor = processor.Right
}
if processor.Right == nil {
res = append(res, root.Val)
processor.Right = root
root = root.Left
} else {
processor.Right = nil
root = root.Right
}
} else {
res = append(res, root.Val)
root = root.Right
}
}
return
}
|
中序
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
| func inorderTraversal(root *TreeNode) (res []int) {
for root != nil {
if root.Left != nil {
processor := root.Left
for processor.Right != nil && processor.Right != root {
processor = processor.Right
}
if processor.Right == nil {
processor.Right = root
root = root.Left
} else {
res = append(res, root.Val)
processor.Right = nil
root = root.Right
}
} else {
res = append(res, root.Val)
root = root.Right
}
}
return
}
|
后序
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
32
33
34
35
36
37
| func postorderTraversal(root *TreeNode) (res []int) {
reveseInts := func(nums []int) {
n := len(nums)
for i := 0; i < n/2; i++ {
nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
}
}
addPath := func(node *TreeNode) {
size := len(res)
for node != nil {
res = append(res, node.Val)
node = node.Right
}
reveseInts(res[size:])
}
for root != nil {
if root.Left != nil {
processor := root.Left
for processor.Right != nil && processor.Right != root {
processor = processor.Right
}
if processor.Right == nil {
processor.Right = root
root = root.Left
} else {
processor.Right = nil
addPath(root.Left)
root = root.Right
}
} else {
root = root.Right
}
}
addPath(root)
return
}
|
结语唠唠
Morris遍历的话，确实可以降低空间复杂度，但是它遍历时改变了二叉树的结构，如果在多线程的场景下，多个线程同时读写(一个写，多个读)某个二叉树的数据，那会非常危险。如果明确要求不可修改二叉树，那这种方案就不适用
有空看能不能补补图(太懒力:|
溜了~~
