当前位置：网站首页>二叉树 | 层序遍历 | 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)
边栏推荐
- TCP连接过程中如果拔掉网线会发生什么？
- 带着昇腾去旅行：一日看尽金陵城里的AI胜景
- 美味的佳肴
- virtual address space
- Self-organization is a two-way journey between managers and members
- ASCII, Unicode and UTF-8
- HanLP词性表
- geemap的详细安装步骤及环境配置
- STL-stack
- August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
猜你喜欢
Detailed installation steps and environment configuration of geemap
2021IDEA创建web工程
测试4年感觉和1、2年时没什么不同？这和应届生有什么区别？
PyQt5 窗口自适应大小
罗克韦尔AB PLC RSLogix5000中计数器指令使用方法介绍
How does the Weiluntong touch screen display the current value of abnormal data while alarming?
阿里云贾朝辉：云XR平台支持彼真科技呈现国风科幻虚拟演唱会
解码2022中国网安强星丨正向建、反向查，华为构建数字化时代的网络安全防线
虚拟地址空间
OneNote tutorial, how to organize notebooks in OneNote?
随机推荐
Self-organization is a two-way journey between managers and members
电力系统潮流计算（牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法）（Matlab代码实现）
【开源教程5】疯壳·开源编队无人机-飞控固件烧写
音乐播放器（未完成版本）
gcc492 compile `.rodata‘ can not be used when making a PIE object； recompile with -fPIE
ASCII, Unicode and UTF-8
Research on multi-element N-k fault model of power system based on AC power flow (implemented by Matlab code) [Power System Fault]
JS use regular expressions in g model and non g difference
QT笔记——用VS + qt 生成dll 和 调用生成的dll
STL-deque
2021 IDEA creates web projects
RecyclerView上下滑动时，不调用onBindViewHolder 导致列表的item不刷新
JS学习 2022080
德科立科创板上市：年营收7.3亿 市值59亿
SDP
Qualcomm Platform Development Series Explanation (Application) Introduction to QCMAP Application Framework
DC-8靶场下载及渗透实战详细过程（DC靶场系列）
Glide监听Activity生命周期源码分析
LeetCode Daily Question (1573. Number of Ways to Split a String)
计算需要的MIPI lane数目