每天分享一个LeetCode题目
每天 5 分钟，一起进步
LeetCode N叉树层序遍历，地址: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
树结点类
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
N叉树的特殊性，就是一个结点可能会包含N个结点，所以，每个结点的孩子结点设置为数组
层序遍历
层序遍历对于很多时候，都是面试经常问到的内容。
尤其是这里有个小点，可能会让大家咯噔一下，就是对于结点的打印方式。
比如，树的结构是：
A
/ | B C D
/|\ / E F G H I
结果打印的方式会有两种：
一种是普通遍历，直接打印
另外一种是每个层级中的元素单独打印，也是LeetCode429 要求的格式
# 第一种
[‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘]
# 第二种
[[‘A‘], [‘B‘, ‘C‘, ‘D‘], [‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘]]
第一种很简单，第二种可能需要一些小小的中间结果记录，咱们分开说说...
第一种层序遍历
1.初始化结果集res，初始化队列queue，将根结点放置到queue中；
2.只要queue不为空，循环遍历，每次遍历将队首元素防止到 res 中，之后将队首元素的孩子结点依次入队；
3.循环执行第 2 点。
看看代码：
def levelOrder_basic(self, root):
# 初始化结果集res
res = []
# 初始化队列queue，将根结点放置到queue中
queue = collections.deque()
queue.appendleft(root)
while(queue):
# 每次遍历将队首元素防止到 res 中
pop_node = queue.pop()
res.append(pop_node.val)
# 将队首元素的孩子结点依次入队
for node in pop_node.children:
queue.appendleft(node)
return res
其实比较简单，就是将遍历到的结点放置到结果集中，同时将结点的孩子结点入队，之后循环进行就好！
第二种层序遍历
这种遍历，有一点难处就是要将每一层级的元素单独放置到数组中，然后将每一层级的数组放置到最后的数组中
这样：
[[‘A‘], [‘B‘, ‘C‘, ‘D‘], [‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘]]
类似于 第一种 层序遍历，需要改变的就是要将每一层级的元素单独遍历
1.初始化结果集res，初始化队列queue，将根结点放置到queue中；
（注意：此处的queue放置的是每一层的结点元素，不理解没关系，往下看）
2.只要queue不为空，循环遍历，同时初始化两个临时数组
? 第一个：tmp_res = []，临时存放每一层遍历访问到的结点，最终会合并到结果res中
? 第二个：tmp_queue = []，临时存放下一层的结点元素，用于下一个循环的遍历
每次遍历将队首元素防止到 tmp_res 中，之后将队首元素的孩子结点依次入队 tmp_queue
最后，将 tmp_queue 赋值给 queue，tmp_res并入到最终结果集 res
3.循环执行第 2 点，直到 queue 为空
4.返回最终结果集 res
看代码
def levelOrder(self, root):
# 最终结果
res = []
if not root:
return res
# 初始化队列，并且将根结点置入队列中
# 存放每一个层级的结点
queue = collections.deque()
queue.appendleft(root)
while(queue):
# 临时存放结点的队列，最终合并到最后的 res 中
tmp_res = []
# 临时存放下一层结点的队列
tmp_queue = []
for node in queue:
tmp_res.append(node.val)
# 将孩子结点放置到 tmp_queue 中
for child_node in node.children:
tmp_queue.append(child_node)
# 将 tmp_queue 赋值给 queue，tmp_res并入到最终结果集 res
queue = tmp_queue
res.append(tmp_res)
看着比较复杂，其实关键有一点，之前循环遍历 queue 就好，现在是把每一层结点动态的赋值给 queue，也就是说每一次循环遍历，queue 中的值是当前层的结点集。
动手画一画就会看起来很简单了哈！
全部代码
# -*- coding:utf-8 -*-
# !/usr/bin/env python
import collections
# 树结点类
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
class Solution(object):
def levelOrder_basic(self, root):
"""
基础的层序遍历，就是把每一层的结点值一次性打印出来
类似于 [‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘] 这样
:param root:
:return:
"""
res = []
queue = collections.deque()
queue.appendleft(root)
while(queue):
pop_node = queue.pop()
res.append(pop_node.val)
for node in pop_node.children:
queue.appendleft(node)
return res
def levelOrder(self, root):
"""
层序遍历(LeetCode中规定的格式)，即把每一层的结点放进各自的数组中
类似于[[‘A‘], [‘B‘, ‘C‘, ‘D‘], [‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘]] 这样
:param root:
:return:
"""
# 最终结果
res = []
if not root:
return res
# 初始化队列，并且将根结点置入队列中
# 存放每一个层级的结点
queue = collections.deque()
queue.appendleft(root)
while(queue):
# 临时存放结点的队列，最终合并到最后的 res 中
tmp_res = []
# 临时存放下一层结点的队列
tmp_queue = []
for node in queue:
tmp_res.append(node.val)
# 将孩子结点放置到 tmp_queue 中
for child_node in node.children:
tmp_queue.append(child_node)
queue = tmp_queue
res.append(tmp_res)
return res
if __name__ == "__main__":
# 新建节点
root = Node(‘A‘)
node_B = Node(‘B‘)
node_C = Node(‘C‘)
node_D = Node(‘D‘)
node_E = Node(‘E‘)
node_F = Node(‘F‘)
node_G = Node(‘G‘)
node_H = Node(‘H‘)
node_I = Node(‘I‘)
# 构建三叉树
# A
# / | # B C D
# /|\ / # E F G H I
root.children = [node_B, node_C, node_D]
node_B.children = [node_E, node_F, node_G]
node_D.children = [node_H, node_I]
s = Solution()
print(s.levelOrder_basic(root))
print(s.levelOrder(root))
可以直接执行哈！