0%

leetcode429 | N叉树层序遍历

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


每天分享一个LeetCode题目

每天 5 分钟,一起进步

LeetCode N叉树层序遍历,地址: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

树结点类

1
2
3
4
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children

N叉树的特殊性,就是一个结点可能会包含N个结点,所以,每个结点的孩子结点设置为数组

层序遍历

层序遍历对于很多时候,都是面试经常问到的内容。

尤其是这里有个小点,可能会让大家咯噔一下,就是对于结点的打印方式。

比如,树的结构是:

1
2
3
4
5
     A
/ | \
B C D
/|\ / \
E F G H I

结果打印的方式会有两种:

一种是普通遍历,直接打印

另外一种是每个层级中的元素单独打印,也是LeetCode429 要求的格式

1
2
3
4
# 第一种
['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 点。

看看代码:

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

其实比较简单,就是将遍历到的结点放置到结果集中,同时将结点的孩子结点入队,之后循环进行就好!

第二种层序遍历

这种遍历,有一点难处就是要将每一层级的元素单独放置到数组中,然后将每一层级的数组放置到最后的数组中

这样:

1
[['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

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 中的值是当前层的结点集。

动手画一画就会看起来很简单了哈!

全部代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# -*- 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))

可以直接执行哈!

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------