当前位置：网站首页>二叉树 | 层序遍历 | leecode刷题笔记
二叉树 | 层序遍历 | leecode刷题笔记
2022-08-10 22:23:00 【Begonia_cat】
文章目录
跟随carl代码随想录刷题
语言：python
carl哥太牛了！！！
二叉树的层序遍历——广度优先
从左到右，一层一层地遍历二叉树。
需要借用队列辅助：
队列先进先出，符合一层一层遍历的逻辑栈先进后出，适合模拟深度优先遍历的逻辑
102. 二叉树的层序遍历
题目：给你二叉树的根节点 root ，返回其节点值的
层序遍历。 （即逐层地，从左到右访问所有节点）。
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
题目分析
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left: # 如果当前节点的左节点存在
que.append(cur.left)
if cur.right: # 如果当前节点的右节点存在
que.append(cur.right)
results.append(result)
return results
107. 二叉树的层序遍历 II
题目：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
题目分析
在104的基础上，把results反转一下就行：return results[::-1]
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(result)
return results[::-1]
199. 二叉树的右视图
题目：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例1：
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
题目分析
在104的基础上，加一条判断：如果当前值是该行最后面的元素，那就放进results数组中。
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
# 写法2：可以直接在这里取`que`的最后一个值
# results.append(que[-1].val)
for i in range(size):
cur = que.popleft()
if i == size-1: # 新代码
results.append(cur.val) # 新代码
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return results
637. 二叉树的层平均值
题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
题目分析
遍历的时候，每层求一个总和，再取平均值。
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
# 求和、取平均
sum = 0
for i in result:
sum += i
results.append(sum/len(result))
return results
求和取平均也可以直接写在for i in range(size):中：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
sum_ = 0 # 新代码
for _ in range(size):
cur = que.popleft()
sum_ += cur.val # 新代码
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(sum_/size) # 新代码
return results
429. N 叉树的层序遍历
题目：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
题目分析
在104的基础上修改：
- 节点有多个孩子
if cur.children: result.extend(children) - python之append、expend函数详解
append是把内容原封不动追加到列表末尾- A = [1, 2]
- B = [3, 4, 5]
- A.append(B)
- A = [1, 2, [3, 4, 5]]
extend是把列表拆开，追加到列表末尾。代码示范：- A = [1, 2]
- B = [3, 4, 5]
- A.extend(B)
- A = [1, 2, 3, 4, 5]
完整代码如下
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.children:
que.extend(cur.children) # 新代码
results.append(result)
return results
515. 在每个树行中找最大值
题目：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
题目分析
在104的基础上进行修改：层序遍历，取最大值。
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
# 取每层最大值
max_ = result[0]
for i in result:
if i > max_:
max_ = i
results.append(max_)
# 上述`取每层最大值`的代码，可以直接用`max()`一行代码实现
# results.append(max(result))
return results
116. 中等填充每个节点的下一个右侧节点指针
题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。
示例 2:
输入：root = []
输出：[]
题目分析
在单层遍历的时候，记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了。
完整代码如下
""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
from collections import deque
que = deque([root])
while que:
size = len(que)
for i in range(size):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
if i == size-1: # 每层最后一个节点指向none，等于默认值，不用做修改
break
cur.next = que[0] # 指向该层前一个节点
return root
117. 填充每个节点的下一个右侧节点指针 II
题目：给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
题目分析
和116题意一样，代码一模一样
104. 二叉树的最大深度
题目：给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
题目分析
返回结果集的长度
if not root: return 0return len(result)
注意：根节点不是叶子节点
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
results = []
if not root:
return 0
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left: # 如果当前节点的左节点存在
que.append(cur.left)
if cur.right: # 如果当前节点的右节点存在
que.append(cur.right)
results.append(result)
return len(results)
111. 二叉树的最小深度
题目：给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
题目分析
只有当左右孩子都为空的时候，才说明遍历到最低点了。
如果其中一个孩子为空则不是最低点。
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
results = []
if not root:
return 0
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left: # 如果当前节点的左节点存在
que.append(cur.left)
if cur.right: # 如果当前节点的右节点存在
que.append(cur.right)
if cur.left == None and cur.right == None:
break # 出现了没有左右孩子的节点，就终止循环
results.append(result) # 记录结果集
if cur.left == None and cur.right == None:
break # 终止while循环
return len(results)
carl的code：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
#根节点的深度为1
queue_ = [(root,1)]
while queue_:
cur, depth = queue_.pop(0)
if cur.left == None and cur.right == None:
return depth
#先左子节点，由于左子节点没有孩子，则就是这一层了
if cur.left:
queue_.append((cur.left,depth + 1))
if cur.right:
queue_.append((cur.right,depth + 1))
return 0
559. 简单N 叉树的最大深度
题目：给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
题目分析
if cur.children: que.extend(cur.children)- 返回
return len(result)
完整代码如下
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
class Solution:
def maxDepth(self, root: 'Node') -> int:
results = []
if not root:
return 0
from collections import deque
que = deque([root])
while(que):
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.children:
que.extend(cur.children)
results.append(result)
return len(results)
222. 完全二叉树的节点个数
题目：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
题目分析
层序遍历，结果全部放入result中，输出len(result)即可。
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
result = []
if not root:
return 0
from collections import deque
que = deque([root])
while que:
size = len(que)
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return len(result)
边栏推荐
- 解码2022中国网安强星丨正向建、反向查，华为构建数字化时代的网络安全防线
- The Thread State,
- RK3399 platform development series explanation (kernel-driven peripherals) 6.35, IAM20680 gyroscope introduction
- Detailed installation steps and environment configuration of geemap
- 企业云存储日常运行维护实践经验分享
- 美味石井饭菜
- 虚拟地址空间
- Addition of linked lists (2)
- fme csmapreprojector转换器使用高程异常模型进行高程基准转换
- Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
猜你喜欢
This visual tool artifact is more intuitive and easy to use!love so much
分享一个后台管理系统可拖拽式组件的设计思路
August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
音乐播放器（未完成版本）
计算需要的MIPI lane数目
合并k个已排序的链表
Distribution Network Expansion Planning: Consider Decisions Using Probabilistic Energy Production and Consumption Profiles (Matlab Code Implementation)
Translating scientific and technological papers, how to translate from Russian to Chinese
实例049：lambda
12 Recurrent Neural Network RNN2 of Deep Learning
随机推荐
2022年8月10日：使用 ASP.NET Core 为初学者构建 Web 应用程序--使用 ASP.NET Core 创建 Web UI（没看懂需要再看一遍）
RecyclerView滑动监听
电力系统潮流计算（牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法）（Matlab代码实现）
JS学习 2022080
【640. Solving Equations】
RK3399平台开发系列讲解（内核驱动外设篇）6.35、IAM20680陀螺仪介绍
解码2022中国网安强星丨正向建、反向查，华为构建数字化时代的网络安全防线
BM13 determines whether a linked list is a palindrome
Leave a message with a prize | OpenBMB x Tsinghua University NLP: The update of the large model open class is complete!
2022年8月的10篇论文推荐
阿里云张新涛：支持沉浸式体验应用快速落地，阿里云云XR平台发布
JS use regular expressions in g model and non g difference
高学历毕业生，该学单片机还是plc？
This visual tool artifact is more intuitive and easy to use!love so much
Detailed installation steps and environment configuration of geemap
BM13判断一个链表是否为回文结构
美味石井饭菜
“数据引擎”开启前装规模量产新赛道，「智协慧同」崭露头角
BM7 list entry in central
谁是边缘计算服务的采购者?是这六个关键角色