【Leetcode刷题Python】102. 二叉树的层序遍历
2023-09-14 09:12:59 时间
1 题目
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
2 解析
(1)方法一:广度优先搜索,递归遍历,用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类
(2)方法二:双端队列,双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们从左往右按顺序拓展。
3 Python实现
(1)方法一
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
def dfs(node,level):
if len(queue_tree)<level:
queue_tree.append([])
queue_tree[level-1].append(node.val)
if node.left is not None:
dfs(node.left,level+1)
if node.right is not None:
dfs(node.right, level+1)
queue_tree = []
dfs(root,1)
return queue_tree
(2)方法二
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
q = deque([root])
res = []
while q and q[0]:
n = len(q)
tmp = []
for _ in range(n):
node = q.popleft()
tmp.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(tmp)
return res
相关文章
- python中pygame怎么安_Python中pygame安装方法图文详解
- python整除和取余写法_Python的整除和取余[通俗易懂]
- python解压bz2文件命令,在Python中解压缩.bz2文件
- Python: 判断某个Excel文件是否已打开
- 【说站】python中如何使用XPath爬取小说
- 【说站】python中Sobel算子是什么
- 【说站】Python dHash算法如何使用
- Python静态代码检查工具Flake8
- python修改第三方库重写_对Python第三方库,再次封装
- Python与Excel:使用xlwings打开Excel文件
- Linux环境下安装Python(linux装python)
- Linux升级:升级Python到最新版本(linux升级python版本)
- 如何在Linux上将Python脚本设置为后台运行?(linux后台运行python)
- python使用ctypes模块调用windowsapi获取系统版本示例