数据结构+算法=程序
程序+设计模式=软件

0%

二叉树的遍历总结

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

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

递归

采用递归是一种很简单的方式,这里以前序遍历为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#定义二叉树类型
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

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

可以看到如果要输出剩下2种遍历方式,只需调整递归的顺序即可,
如果不采用递归,而采用迭代的方式应该如何实现呢?

迭代

前序遍历
1
2
3
4
5
6
7
8
9
10
11
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[root]
while stack:
n=stack.pop()
if not n:
continue
res.append(n.val)
stack.append(n.right)
stack.append(n.left)
return res
后序遍历
1
2
3
4
5
6
7
8
9
10
11
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[root]
while stack:
n=stack.pop()
if not n:
continue
res.append(n.val)
stack.append(n.left)
stack.append(n.right)
return res[::-1]

后序遍历这里稍微用了点“作弊”的方式,修改了前序遍历的顺序,然后将结果逆序输出,并不是直接按后序顺序输出的。当然也有直接迭代的方法,不过有点复杂,本文没有深究,后面会提到一种迭代的通用办法。

中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
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

中序遍历稍微有点复杂,需要多定义一个curr来指向下一个要遍历的节点,总的来说采用迭代会需要利用一个栈空间来辅助。

迭代通用法

不管哪种顺序都可以采用此方法,只需修改stack的添加顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

这里需要给每个节点添加一个额为的状态:0表示未访问,1表示已访问,第一次进栈的节点都是未访问状态,只有第二次进栈才会标记为已访问。
进栈顺序决定了下次要访问的节点,也就决定了输出顺序,而只有当出栈的节点是已标记过的才会将其输出。