DFS
- 处理当前节点的位置不同对应着不同的遍历
def preorderTraversal(root):
if not root:
return
print(root.val) #前序遍历，处理当前节点
preorderTraversal(root.left) # 递归遍历左子树
print(root.val) #中序遍历，处理当前节点
preorderTraversal(root.right)# 递归遍历右子树
print(root.val) #后序遍历，处理当前节点
BFS
-
BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS总共有两个模板：
-
如果不需要确定当前遍历到了哪一层，BFS模板如下
while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)
- 如果要确定当前遍历到了哪一层，BFS模板如下
level = 0 #表示当前遍历到二叉树中的哪一层了
while queue 不空：
size = queue.size() #size表示在当前遍历层有多少个元素
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
level ++;