python - bfs 遍历二叉树的性能
问题描述
我正在练习 二叉树级别顺序遍历问题 - LeetCode
给定一棵二叉树,返回其节点值的级别顺序遍历。(即,从左到右,逐级)。
例如:给定二叉树
[3,9,20,null,null,15,7]
,3 / \ 9 20 / \ 15 7
将其水平顺序遍历返回为:
[ [3], [9,20], [15,7] ]
BFS 解决方案
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if root == None: return []
queue = deque([root])
res = []
step = -1
while queue:
step += 1
size = len(queue)
if len(res) < step + 1:
res.append([])
for _ in range(size):
cur = queue.popleft()
res[step].append(cur.val)
#stretch
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
表演者
运行时间:44 毫秒,比二叉树级顺序遍历的 Python3 在线提交的 75.27% 快。
内存使用:13.4 MB,不到二叉树级顺序遍历的 Python3 在线提交的 5.64%。
请注意繁琐的检查:
if len(res) < step + 1:
res.append([])
删除条件检查后
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if root == None: return []
queue = deque([root])
res = []
step = -1
while queue:
step += 1
size = len(queue)
# if len(res) < step + 1: #remove the condition checking
res.append([])
for _ in range(size):
cur = queue.popleft()
res[step].append(cur.val)
#stretch
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
表演改为
运行时间:56 毫秒,比二叉树级顺序遍历的 Python3 在线提交的 19.04% 快。
内存使用:13.5 MB,不到二叉树级顺序遍历的 Python3 在线提交的 4.52%。
从逻辑上讲,它们具有相同的性能,为什么会报告如此大的差异?
解决方案
推荐阅读
- java - MongoDB:“MongoSocketException:mongodb:提供节点名或服务名,或未知”
- sql-server - SQL Server:引用其他视图的视图列表
- javascript - API 和接口(对象类型)如何可供 JavaScript 使用?
- javascript - 将参数传递到 URL
- java - Java:ImageIcon - 图像文件更新,但 Java 框架中的图像图标没有
- android - 步进器内的日期选择器
- laravel - 通过回答安全问题手动重置密码而不发送电子邮件 - Laravel/auth
- r - 如何在ggplot lineplot中为具有相似颜色的多个子类着色?
- date - Applescript:通过添加具有奇怪行为的天数来增加月份
- c# - 使用 SQL Server CE 数据库部署 .exe 时遇到问题