-
二叉树 | 层序遍历 | leecode刷题笔记
文章目录
跟随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- 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
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]- 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
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- 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
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- 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
求和取平均也可以直接写在
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- 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
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- 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
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- 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
116.
中等填充每个节点的下一个右侧节点指针题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }- 1
- 2
- 3
- 4
- 5
- 6
填充它的每个 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- 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
117. 填充每个节点的下一个右侧节点指针 II
题目：给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }- 1
- 2
- 3
- 4
- 5
- 6
填充它的每个 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)- 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
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)- 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
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- 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
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)- 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
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)- 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
404. 左叶子之和
题目：给定二叉树的根节点 root ，返回所有左叶子之和。
题目分析
本题统计的是
左叶子而不是每层的左端点喔
所以，需要加一个判断条件：- 如果当前节点
cur的左节点存在， - 并且
左节点的左孩子和左节点的右孩子都不存在 - 则
cur.left是左节点，可以加入结果集result += cur.left.val
完整代码如下
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: result = 0 if not root: return 0 que = deque([root]) while que: cur = que.popleft() # size = len(que) # for _ in size: if cur.left and not cur.left.left and not cur.left.right: result += cur.left.val if cur.left: que.append(cur.left) if cur.right: que.append(cur.right) return result- 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
513. 找树左下角的值
题目：给定一个二叉树的
根节点 root，请找出该二叉树的最底层 最左边节点的值。假设二叉树中至少有一个节点。
题目分析
输出最后一层的第一个值
return result[-1][0]完整代码如下
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int: results = [] if not root: return None 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][0]- 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
在上述代码中修改一下，队列可以做的，栈也可以，毕竟这个题不讲究顺序嘛
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: result = 0 if not root: return 0 stack = [] stack.append(root) while stack: cur = stack.pop() if cur.left and not cur.left.left and not cur.left.right: result += cur.left.val if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) return result- 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
-
相关阅读:
普通人下半年做电商还有机会吗？
2022/8/8 比赛思维+状压dp
（二）k8-集群创建
文件操作和IO
Appium的使用教程
【黄色手套22】13番外：第一个C语言程序
Python与Scrapy：构建强大的网络爬虫
搜狗百科词条创建报价为何跨度这么大？
024 - STM32学习笔记 - 液晶屏控制（一） - LTDC与DMA2D初始
python绘制云雨图(raincloud plot) 【官方教程翻译】
- 原文地址：https://blog.csdn.net/qq_44250700/article/details/126263962
