无锡网站排名优化报价,2024房地产最新消息,wordpress海报插件,上海建设银行网站静安支行题目描述#xff08;简要概括#xff09;
题目链接#xff1a;102. 二叉树的层序遍历 - 力扣#xff08;LeetCode#xff09;
题目要求对给定的二叉树进行层序遍历#xff08;从上到下#xff0c;从左到右#xff09;#xff0c;并返回遍历的结果。层序遍历是一种基…题目描述简要概括
题目链接102. 二叉树的层序遍历 - 力扣LeetCode
题目要求对给定的二叉树进行层序遍历从上到下从左到右并返回遍历的结果。层序遍历是一种基于广度优先搜索BFS的遍历方式通常使用队列来实现。
输入输出 输入二叉树的根节点 root。 输出一个二维列表表示每一层的节点值。
解题思路 使用队列实现 BFS 初始化一个队列将根节点加入队列。 每次从队列中取出一层的节点记录它们的值并将它们的子节点加入队列。 重复上述过程直到队列为空。 记录每一层的节点值 使用一个列表来存储每一层的节点值。 最终将所有层的节点值组合成一个二维列表作为结果。 代码详细解析
from collections import dequeclass TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef list_to_tree(data):if not data:return Noneroot TreeNode(data[0])queue [root]index 1while queue and index len(data):node queue.pop(0)if index len(data) and data[index] is not None:node.left TreeNode(data[index])queue.append(node.left)index 1if index len(data) and data[index] is not None:node.right TreeNode(data[index])queue.append(node.right)index 1return rootdef levelOrder(root):if not root:return []result []queue deque([root])while queue:level_size len(queue)current_level []for _ in range(level_size):node queue.popleft()current_level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(current_level)return resultif __name__ __main__:data [3, 9, 20, None, None, 15, 7]root list_to_tree(data)result levelOrder(root)print(result) # 输出[[3], [9, 20], [15, 7]] 示例解析
假设输入的二叉树如下
复制 3/ \9 20/ \15 7 初始化 队列[3] 结果[] 第一层根节点 当前层[3] 队列[9, 20] 结果[[3]] 第二层 当前层[9, 20] 队列[15, 7] 结果[[3], [9, 20]] 第三层 当前层[15, 7] 队列[] 结果[[3], [9, 20], [15, 7]] 返回结果 [[3], [9, 20], [15, 7]] 总结
通过使用队列实现 BFS我们可以轻松地完成二叉树的层序遍历。每层的节点值按顺序加入结果列表最终返回一个二维列表。希望这个解析对你有帮助如果有任何问题欢迎随时提问。
