Как работают 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 -> rightDFS 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 -> nodePostorder нужен, когда ответ узла зависит от ответов детей: высота дерева, удаление дерева, подсчет размера поддерева.
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.