BFS 检索每个顺序中值的元素
BFS to retrieve elements of values in each order
我尝试解决问题Binary Tree Level Order Traversal - LeetCode
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
我的解决方案很直观,BFS遍历并收集每一层的值
from collections import deque
class Solution:
def levelOrder(self, root):
if not root: return [] #base case
res = []
#queue to colloct all the nodes
queue = deque([root])
while queue:
level_vals = [] #hold the values at the current level.
for _ in range(len(queue)): #evalute once before execution enter the loop
cur = queue.popleft()
if node.left:
queue.append(cur.left)
if node.right:
queue.append(cur.right)
level_vals.append(cur.val)
res.append(level_vals)
return res
我在讨论区看到了这样的bfs和queue soltion
# BFS + deque
def levelOrder(self, root):
res, queue = [], deque([(root, 0)])
while queue:
cur, level = queue.popleft()
if cur:
if len(res) < level+1:
res.append([])
res[level].append(cur.val)
queue.append((cur.left, level+1))
queue.append((cur.right, level+1))
return res
我对条件检查感到困惑if len(res) < level+1: res.append([])
,并认为它可以是'
if cur:
#if len(res) < level+1:
res.append([])
res[level].append(cur.val)
queue.append((cur.left, level+1))
queue.append((cur.right, level+1))
return res
为什么需要条件检查?
只有在 queue
中遇到新级别时,才会将新数组(对应于新级别)附加到 res
中。如果没有该检查,代码将为 queue
.
中遇到的每个节点向 res
附加一个新的空数组
让我们看看当您 运行 带有条件检查的代码时会发生什么。对于您的示例树,首先从队列中弹出值为 3 的根节点。此时res
的长度为0,level
也为0。所以 len(res) > level + 1
是真的。因此,一个新的空数组被附加到 res
以存储树级别 0 的值。处理级别 1 的第一个节点(值为 9)时也是如此。但是处理完之后,当我们开始处理level 1的第二个节点(值为20)时,res
数组有2个元素(每个level一个),level的值为1。 len(res) > level + 1
为假,没有任何内容插入到 res
.
如果没有这个检查,res 数组在迭代结束时会是这样的:
[
[3],
[9, 20],
[15, 7],
[],
[]
]
请注意,因为您的树中有 5 个节点,所以总共有 5 个数组附加到 res
但只有前 3 个被占用,因为您的树有 3 个级别。
我尝试解决问题Binary Tree Level Order Traversal - LeetCode
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree
[3,9,20,null,null,15,7]
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
我的解决方案很直观,BFS遍历并收集每一层的值
from collections import deque
class Solution:
def levelOrder(self, root):
if not root: return [] #base case
res = []
#queue to colloct all the nodes
queue = deque([root])
while queue:
level_vals = [] #hold the values at the current level.
for _ in range(len(queue)): #evalute once before execution enter the loop
cur = queue.popleft()
if node.left:
queue.append(cur.left)
if node.right:
queue.append(cur.right)
level_vals.append(cur.val)
res.append(level_vals)
return res
我在讨论区看到了这样的bfs和queue soltion
# BFS + deque
def levelOrder(self, root):
res, queue = [], deque([(root, 0)])
while queue:
cur, level = queue.popleft()
if cur:
if len(res) < level+1:
res.append([])
res[level].append(cur.val)
queue.append((cur.left, level+1))
queue.append((cur.right, level+1))
return res
我对条件检查感到困惑if len(res) < level+1: res.append([])
,并认为它可以是'
if cur:
#if len(res) < level+1:
res.append([])
res[level].append(cur.val)
queue.append((cur.left, level+1))
queue.append((cur.right, level+1))
return res
为什么需要条件检查?
只有在 queue
中遇到新级别时,才会将新数组(对应于新级别)附加到 res
中。如果没有该检查,代码将为 queue
.
res
附加一个新的空数组
让我们看看当您 运行 带有条件检查的代码时会发生什么。对于您的示例树,首先从队列中弹出值为 3 的根节点。此时res
的长度为0,level
也为0。所以 len(res) > level + 1
是真的。因此,一个新的空数组被附加到 res
以存储树级别 0 的值。处理级别 1 的第一个节点(值为 9)时也是如此。但是处理完之后,当我们开始处理level 1的第二个节点(值为20)时,res
数组有2个元素(每个level一个),level的值为1。 len(res) > level + 1
为假,没有任何内容插入到 res
.
如果没有这个检查,res 数组在迭代结束时会是这样的:
[
[3],
[9, 20],
[15, 7],
[],
[]
]
请注意,因为您的树中有 5 个节点,所以总共有 5 个数组附加到 res
但只有前 3 个被占用,因为您的树有 3 个级别。