BFS для извлечения элементов значений в каждом порядке
Пробовал решить проблему Обход порядка двоичного дерева - 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 7return 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 и очереди в Дискуссионной Зоне.
# 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
Зачем нужна проверка состояния?
Ответы 1
Проверка условия существует, так что новый массив (соответствующий новому уровню) добавляется к res только тогда, когда в queue встречается новый уровень. Без этой проверки код добавлял бы новый пустой массив к res для каждого узла, встречающегося в queue.
Давайте посмотрим, что произойдет, когда вы запустите код с проверкой условия. Для вашего примера дерева сначала из очереди выталкивается корневой узел со значением 3. В это время длина res равна 0, и level тоже 0. Так что len(res) > level + 1 верно. Таким образом, к res добавляется новый пустой массив для хранения значений для уровня дерева 0. То же самое происходит, когда обрабатывается первый узел уровня 1 (со значением 9). Однако после его обработки, когда мы начинаем обрабатывать второй узел уровня 1 (со значением 20), массив res имеет 2 элемента (по одному на каждый уровень) и значение уровня равно 1. len(res) > level + 1 ложно и ничего не вставляется. к res.
Без этой проверки массив res был бы примерно таким в конце итерации:
[
[3],
[9, 20],
[15, 7],
[],
[]
]
Обратите внимание, что, поскольку в вашем дереве 5 узлов, к res добавляется всего 5 массивов, но заняты только 3 верхних, потому что ваше дерево имеет 3 уровня.