数据结构+算法=程序
程序+设计模式=框架

0%

二叉树的通用遍历模板

遍历一棵二叉树,主要分为前序遍历、中序遍历和后序遍历三种方式,不同的方式输出的顺序不同:

  • 前序遍历: 根节点->左节点->右节点
  • 中序遍历: 左节点->根节点->右节点
  • 后序遍历: 左节点->右节点->根节点

本文将介绍递归迭代标记迭代以及莫里斯迭代四种方式的通用模板,对二叉树分别进行前中后序遍历,以及每种方式的特点。
首先先定义二叉树结构:

1
2
3
4
5
6
#定义二叉树类型
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

递归

递归是二叉树遍历中最简单的方式:

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
#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
def dfs(n):
if not n:
return
res.append(n.val)
dfs(n.left)
dfs(n.right)
dfs(root)
return res

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
def dfs(n):
if not n:
return
dfs(n.left)
res.append(n.val)
dfs(n.right)
dfs(root)
return res

#后序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
def dfs(n):
if not n:
return
dfs(n.left)
dfs(n.right)
res.append(n.val)
dfs(root)
return res

可以看到对于不同的遍历顺序,只需调整递归的顺序即可。
递归的时间复杂度是O(n) ,n为节点数,每个节点恰好访问一次。
空间复杂度是O(logn),也就是树的高度。因为在递归过程中会用到logn的栈空间,如果一棵树所有节点都只有右节点或左节点,也就是说变成了一个链表,那么会用到O(n)的栈空间,所以在最坏情况下,空间复杂度是O(n)。

迭代

普通迭代的代码实现虽然不复杂,但却难以理解,它需要使用一个辅助栈来临时存储遍历的节点,遍历顺序为先找到最左节点,并将沿途遇到的节点全缓存进栈,然后从栈中依次弹出作为当前节点,然后再将该节点的右节点置为当前节点。

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
#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[]
curr=root
while curr or stack:
while curr:
stack.append(curr)
curr=curr.left
curr=stack.pop()
res.append(curr.val)
curr=curr.right
return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[]
curr=root
while curr or stack:
while curr:
res.append(curr.val)
stack.append(curr)
curr=curr.left
curr=stack.pop()
curr=curr.right
return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[]
curr=root
while curr or stack:
while curr:
res.append(curr.val)
stack.append(curr)
curr=curr.right
curr=stack.pop()
curr=curr.left
return res[::-1]

后序遍历这里用了点“作弊”的方式,修改了前序遍历的顺序(根-左-右),变成了(根-右-左),然后将结果逆序(左-右-根),并不是直接按后序顺序输出的。当然也有直接迭代的方法,不过实现起来很复杂,本文只想介绍一种通用模板,所以并没有深究。
迭代的时间复杂度也是O(n),n为节点数。
空间复杂度是O(logn),即树的高度,其辅助栈空间取决于树的结构,最坏情况会存储整棵树,即O(n)。

标记迭代

相较于普通迭代,标记迭代显得更容易理解,它除了在辅助栈中缓存节点外,还额外记录了这个节点的状态(0、1表示),0表示未访问,1表示已访问,第一次进栈的节点都是未访问状态,只有第二次进栈才会标记为已访问。
如果节点从栈中弹出的时候状态是0,那么就将它的左右节点继续入栈,同时将它本身的状态设置为1;如果节点从栈中弹出的时候状态是1,那么就将该节点打印出来。
进栈顺序决定了下次要访问的节点,也就决定了输出顺序,而只有当出栈的节点是已标记过的才会将其输出。

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
#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[(root,0)]
while stack:
n,s=stack.pop()
if not n:
continue
if s==0:
stack.append((n.right,0))
stack.append((n,1))
stack.append((n.left,0))
else:
res.append(n.val)
return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[(root,0)]
while stack:
n,s=stack.pop()
if not n:
continue
if s==0:
stack.append((n.right,0))
stack.append((n.left,0))
stack.append((n,1))
else:
res.append(n.val)
return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[(root,0)]
while stack:
n,s=stack.pop()
if not n:
continue
if s==0:
stack.append((n,1))
stack.append((n.right,0))
stack.append((n.left,0))
else:
res.append(n.val)
return res

采用标记迭代,遍历三种顺序就和递归方式一样,代码几乎完全一样,只需更改顺序即可。
它的时间复杂度依然是O(n),不过需要2倍的普通迭代的栈空间,空间复杂度依然可看作是O(logn)。

莫里斯(Morris)迭代

前面介绍的三种方式都需要使用额外的空间,而莫里斯迭代是一种采用时间换空间的方法,它并不需要额外的空间作为临时存储,不过代价就是每个节点可能会被访问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
49
50
51
52
53
54
55
56
57
58
59
#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
while root:
tail=root.left
if tail:
while tail.right and tail.right!=root:
tail=tail.right
if tail.right: #tail.right==root
res.append(root.val)
tail.right=None
else: #tail.right==None
tail.right=root
root=root.left
continue
else:
res.append(root.val)
root=root.right
return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
while root:
tail=root.left
if tail:
while tail.right and tail.right!=root:
tail=tail.right
if tail.right: #tail.right==root
tail.right=None
else: #tail.right==None
res.append(root.val)
tail.right=root
root=root.left
continue
else:
res.append(root.val)
root=root.right
return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
while root:
tail=root.right
if tail:
while tail.left and tail.left!=root:
tail=tail.left
if tail.left: #tail.left==root
tail.left=None
else: #tail.left==None
res.append(root.val)
tail.left=root
root=root.right
continue
else:
res.append(root.val)
root=root.left
return res[::-1]

在莫里斯迭代中,后序遍历可看作是前序遍历的完整镜像,所有涉及到左右子节点的地方都进行互换,最后得到根-右-左的序列,再将结果集反转变成左-右-根的序列。
莫里斯迭代的所有左子节点会被访问2次,由于是常数,所以时间复杂度依然可看作是O(n),但是它不借助任何额外空间,所以空间复杂度是O(1)。