当前位置：网站首页>二叉树 | 层序遍历 | 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)
边栏推荐
猜你喜欢
常用代码扩展点设计方式
实例054：位取反、位移动
GMT,UTC,CST,DST,RTC,NTP,SNTP,NITZ: 嵌入式的时间
OneNote tutorial, how to organize notebooks in OneNote?
DC-7靶场下载及渗透实战详细过程（DC靶场系列）
MySQL：MySQL的集群——主从复制的原理和配置
QT笔记——vs + qt 创建一个带界面的 dll 和 调用带界面的dll
EL表达式
新一代网络安全防护体系的五个关键特征
Power system power flow calculation (Newton-Raphson method, Gauss-Seidel method, fast decoupling method) (Matlab code implementation)
随机推荐
web项目访问引用jar内部的静态资源
Lambda
12 Recurrent Neural Network RNN2 of Deep Learning
Research on multi-element N-k fault model of power system based on AC power flow (implemented by Matlab code) [Power System Fault]
阿里云架构师金云龙：基于云XR平台的视觉计算应用部署
华为HCIE云计算之Fusion Access桌面云
QT笔记——vs + qt 创建一个带界面的 dll 和 调用带界面的dll
3598. 二叉树遍历(华中科技大学考研机试题)
高学历毕业生，该学单片机还是plc？
阿里云贾朝辉：云XR平台支持彼真科技呈现国风科幻虚拟演唱会
leetcode：355. 设计推特
美味的佳肴
新一代网络安全防护体系的五个关键特征
瑞幸咖啡第二季营收33亿：门店达7195家 更换CFO
“数据引擎”开启前装规模量产新赛道，「智协慧同」崭露头角
2021IDEA创建web工程
文件IO-缓冲区
实例055：按位取反
元宇宙社交应用，靠什么吸引用户「为爱发电」？
Leave a message with a prize | OpenBMB x Tsinghua University NLP: The update of the large model open class is complete!