re:re:actable
Урок 033 минуты чтения

Как работают DFS и BFS для дерева?

На этой странице
Кратко

DFS идет в глубину и обычно реализуется рекурсией или стеком. BFS идет по уровням и использует очередь. Для дерева оба обхода посещают каждый узел за O(n), но порядок и память отличаются.

Вопрос

Как работают DFS и BFS для дерева и чем отличаются обходы pre-order, in-order, post-order?

Одно дерево - четыре порядка

        1
      /   \
     2     3
    / \
   4   5
ОбходПравилоРезультат
Preorderузел, левое, правое1, 2, 4, 5, 3
Inorderлевое, узел, правое4, 2, 5, 1, 3
Postorderлевое, правое, узел4, 5, 2, 3, 1
Level order (BFS)по уровням слева направо[1], [2, 3], [4, 5]

Три DFS-обхода отличаются только тем, в какой момент мы записываем значение узла: до детей, между ними или после.

DFS preorder

function preorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (!root) return result
 
  result.push(root.value)
  preorder(root.left, result)
  preorder(root.right, result)
 
  return result
}

Порядок:

node -> left -> right

DFS inorder

function inorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (!root) return result
 
  inorder(root.left, result)
  result.push(root.value)
  inorder(root.right, result)
 
  return result
}

Для BST дает значения в sorted order.

DFS postorder

function postorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (!root) return result
 
  postorder(root.left, result)
  postorder(root.right, result)
  result.push(root.value)
 
  return result
}

Порядок:

left -> right -> node

Postorder нужен, когда ответ узла зависит от ответов детей: высота дерева, удаление дерева, подсчет размера поддерева.

BFS level order

function levelOrder(root: TreeNode<number> | null): number[][] {
  if (!root) return []
 
  const result: number[][] = []
  const queue = [root]
  let head = 0
 
  while (head < queue.length) {
    const levelSize = queue.length - head
    const level: number[] = []
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++]
      level.push(node.value)
 
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
 
    result.push(level)
  }
 
  return result
}

levelSize фиксирует, сколько узлов в очереди принадлежит текущему уровню. Дети, добавленные во время цикла, относятся уже к следующему уровню и обработаются на следующей итерации while.

Что отвечать на собеседовании?

DFS обходит дерево в глубину и подходит для рекурсивных задач: depth, path sum, validate tree. BFS обходит по уровням и использует queue: level order, minimum depth, nearest node. Оба обхода по времени O(n), потому что посещают каждый узел один раз.

Что важно помнить: частые ошибки

  • Использовать shift() в BFS.
  • Забывать base case null.
  • Путать preorder/inorder/postorder.
  • Не учитывать call stack в DFS.
  • Неправильно считать levelSize.

Мини-шпаргалка

  • DFS - stack/recursion.
  • BFS - queue.
  • Preorder: node-left-right.
  • Inorder: left-node-right.
  • Postorder: left-right-node.
  • Level order - BFS.

Документация

Wikipedia: Tree traversal.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам