# 【完虐算法系列】讲透树-2 | 树的遍历复盘专题

## 1 前言

102.二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal

589.N 叉树的前序遍历 https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal

107.二叉树的层序遍历 II https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii

145.二叉树的后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal

94.二叉树的中序遍历 https://leetcode-cn.com/problems/binary-tree-inorder-traversal

429.N 叉树的层序遍历 https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal

144.二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal

590.N 叉树的后序遍历 https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal

## 3 递归遍历

```# 二叉树
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

# N叉树
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children```

```# 二叉树
class TreeNode(object):
def __init__(self, val, children=[]):
self.val = val
self.children = children```

```# 二叉树
res = []
def pre_order(root):
if not root:
return
res.append(root.val)
pre_order(root.left)
pre_order(root.right)

# N叉树
res = []
def pre_order(root):
if not root:
return
res.append(root.val)
for node in root.children:
pre_order(node)```

N叉树的写法是，利用 `for` 循环，依次递归孩子结点。

github 查看详细代码：https://github.com/xiaozhutec/share_leetcode

## 4 非递归遍历

```# 经典层次遍历打印形式
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
# LeetCode 中打印的形式
[['A'], ['B', 'C', 'D'], ['E', 'F', 'G', 'H', 'I']]```

#### 传统层次遍历打印形式

```while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)```

```while queue:
node = queue.pop()
res.append(node.val)
for child_node in node.children:
queue.appendleft(child_node)```

#### LeetCode 中题目打印方式

queue 中存放的是当前层的结点集，level_queue 存放的下一层的结点集合。

「点击下图查看高清原图」👇

```def levelOrder(self, root):
res = []
if not root:
return res
queue = [root]
while queue:
level_queue = []      # 临时记录每一层结点
level_res = []        # 临时记录每一行的结点值
for node in queue:		# 循环遍历每一层所有的结点
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res```

```def levelOrder_leetcode(self, root):
res = []
queue = [root]
if not root:
return res
while queue:
level_queue = []  	# 临时保存每一层结点元素便于下一次进行迭代
level_res = []    	# 临时保存每一层结点值
for node in queue:
level_res.append(node.val)
if node.children:
for child_node in node.children:
level_queue.append(child_node)
queue = level_queue
res.append(level_res)
return res```

github 内容刚刚开始更新，感兴趣的可以一起来学习。私信我 “LeetCode刷题” 群里一起刷题进步。

(0)

01771
Johngo学长
2021年10月13日

23471
Johngo学长
2021年9月17日

03321
Johngo学长
2021年10月20日

02310
Johngo学长
2021年11月4日

03182
Johngo学长
2021年10月13日

12801
Johngo学长
2021年9月27日