0%

LeetCode102 | 二叉树的中序遍历

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


每天分享一个LeetCode题目

每天 5 分钟,一起进步!

LeetCode 层序遍历,地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

树结点类

1
2
3
4
5
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

层序遍历

层序遍历比较重要!

第一点,层序本身就是一种 BFS 的思想,作为最为基础的一个题目,校招中很多时候会被问到;

第二点,在解决一些其他类型的题目的时候,BFS 的思想可以作为很多题目的基础解法,这个在后面的题目中会很多次的用到。

通常解法思路(利用队列进行辅助):

1.初始化一个队列queue,然后将头结点入队;

2.队列 queue 出队首元素 node,并且打印

3.判断结点 node 是否有左右孩子。如果有,左右孩子依次入队,然后执行第 2 点。否则,直接执行第 2 点

实现的代码

1
2
3
4
5
6
7
8
9
10
11
def level_order_traverse(self, head):
if not head:
return
queue = [head]
while len(queue) > 0:
tmp = queue.pop(0)
print(tmp.value, end=" ")
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)

而题目中,要求是这样的形式输出。即:将每一行作为一个列表输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
二叉树:[3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回其层序遍历结果:

[
[3],
[9,20],
[15,7]
]

咱么应该在输出的部分做一些改变,需要在遍历到每行的时候,进行单独保存,之后合并到最终的数组当中。

单独保存的部分,进行循环遍历,将下一层的结点更新到另外一个数组当中。

看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def levelOrder(self, root):
res = []
if not root:
return res
queue = [root]
while queue:
tmp_queue = [] # 临时记录每一层结点
tmp_res = [] # 临时记录每一行的结点值
for node in queue:
tmp_res.append(node.val)
if node.left:
tmp_queue.append(node.left)
if node.right:
tmp_queue.append(node.right)
queue = tmp_queue
res.append(tmp_res)
return res

其实就是做了一个很小的操作即可实现

完整代码

包括测试案例

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
# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 树结点类
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right


class Solution(object):
def levelOrder(self, root):
res = []
if not root:
return res
queue = [root]
while queue:
tmp_queue = [] # 临时记录每一层结点
tmp_res = [] # 临时记录每一行的结点值
for node in queue:
tmp_res.append(node.val)
if node.left:
tmp_queue.append(node.left)
if node.right:
tmp_queue.append(node.right)
queue = tmp_queue
res.append(tmp_res)
return res


if __name__ == "__main__":
# 新建节点
root = TreeNode('A')
node_B = TreeNode('B')
node_C = TreeNode('C')
node_D = TreeNode('D')
node_E = TreeNode('E')
node_F = TreeNode('F')
node_G = TreeNode('G')
node_H = TreeNode('H')
node_I = TreeNode('I')
# 构建二叉树
# A
# / \
# B C
# / \ / \
# D E F G
# / \
# H I
root.left, root.right = node_B, node_C
node_B.left, node_B.right = node_D, node_E
node_C.left, node_C.right = node_F, node_G
node_D.left, node_D.right = node_H, node_I

s = Solution()
print(s.levelOrder(root))

最后

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

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