BFS для извлечения элементов значений в каждом порядке - PullRequest
Новая
       15

BFS для извлечения элементов значений в каждом порядке

1 голос
/ 10 апреля 2019

Я пытался решить проблему Обход порядка двоичного дерева - LeetCode

Для заданного двоичного дерева вернуть уровень порядка обход значений его узлов. (то есть слева направо, уровень за уровнем).

Например: Дано бинарное дерево [3,9,20,null,null,15,7], 

    3
   / \
  9  20
    /  \
   15   7

возвращает порядок обхода уровня как: 

[
  [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 в Области обсуждения 

# 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 Ответ

2 голосов
/ 10 апреля 2019

Проверка состояния выполняется таким образом, что новый массив (соответствующий новому уровню) добавляется к 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 равно false и ничего не вставляется в res.

Без этой проверки массив res будет примерно таким в конце итерации: 

[
  [3],
  [9, 20],
  [15, 7],
  [],
  []
]

Обратите внимание, что, поскольку в вашем дереве 5 узлов, к res добавляется всего 5 массивов, но только три верхних заняты, поскольку в вашем дереве 3 уровня.

...