2 техники решения задач обхода дерева

Мотивация

Дерево — одна из самых популярных структур данных при кодировании интервью, поэтому важно понимать методы обхода дерева.

1. Поиск в ширину

Давайте посмотрим на эту проблему:

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

Источник: Литкод

Почему поиск в ширину (BFS) идеально подходит для решения этой проблемы?

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

Что требуется для поиска с первым дыханием (BFS)?

В поиске в ширину (BFS) у нас есть очередь для отслеживания следующего элемента, который будет посещать алгоритм. Всякий раз, когда мы исследуем узел, все его дочерние узлы на следующем уровне будут перемещаться в очередь для последующего изучения.

Что такое пространственно-временная сложность BFS?

Сложность времени, очевидно, O (N), где N — общее количество узлов в дереве, поскольку мы должны посетить каждый узел один раз.

Сложность пространства: O(N), так как нам нужна очередь для отслеживания списка следующих узлов для посещения.

Как применить BFS к описанной выше проблеме?

Теперь это просто, когда вы понимаете BFS. Мы можем создать массив и добавить все узлы на каждом уровне, прежде чем мы исключим из очереди, чтобы исследовать этот узел и поставить в очередьего дочерние узлы. Ниже приведена реализация на JavaScript

Похожие задачи на практике:



Обход зигзагообразного порядка на уровне двоичного дерева — LeetCode
Для корня бинарного дерева возвратите обход значений его узлов в зигзагообразном порядке. (т. е. слева направо…leetcode.com





Обход порядка на уровне двоичного дерева II — LeetCode
По заданному корню двоичного дерева возвратить обход по порядку восходящего уровня значений его узлов. (т. е. слева направо…leetcode.com



2. Поиск в глубину (DFS)

Давайте посмотрим на эту проблему:

Учитывая root бинарного дерева и целое число targetSum, вернуть true, если дерево имеет путь от корня к листу, такой что сумма всех значений пути равна targetSum.

Листок — это узел без дочерних элементов.

Источник: Литкод

Почему DFS является идеальным решением этой проблемы, а не BFS?

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

Что требуется для DFS?

Рекурсия — это принцип, лежащий в основе BFS, поскольку алгоритм идет от корня к листьям, затем возвращается обратно и исследует другие пути в дереве. Обратите внимание, что когда речь идет о рекурсии, она будет включать стек.

Что такое пространственно-временная сложность DFS?

Поскольку целью DFS является посещение всех узлов дерева, временная сложность, очевидно, равна O(N), где N — общее количество >количество узлов внутри дерева.

Пространственная сложность: O(N), так как мы используем рекурсию, которая использует стек для хранения посещенных узлов.

Как применить DFS к проблеме?

Пусть sum представляет оставшуюся сумму пути от текущего узла до конечного узла до того, как текущий узел будет принят во внимание. Для листового узла нам нужно сделать sum - root.val == 0

Take input of example 1 tree as above, we can trace DFS as below:
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
The basic idea is to recursively call to leaf node and check if leaf node value is equal to the remaining sum. 
1. Start DFS from root (5), Sum = 22 
2. Call recursive call to left node -> visit 4, Sum = 22 - 5 = 17
3. Call recursive call to left node -> visit 11, Sum = 17 - 4 = 13
6. Recursive call to left node -> 7(leaf),Sum = 13 - 11 =2#7->false
7. Recursively back to 11, sum = 13
8. Recursive call to right node -> 2 (leaf), Sum =13-1=2-> True

См. реализацию JavaScript, как показано ниже:

Похожие задачи на практике:



Сумма путей III — LeetCode
По заданному корню бинарного дерева и целочисленному targetSum вернуть количество путей, где сумма значений вдоль…leetcode .com





Самый длинный путь с однозначным значением — LeetCode
По корню бинарного дерева вернуть длину самого длинного пути, где каждый узел пути имеет одно и то же значение…leetcode.com



Заключение

BFS и DFS — два очень мощных метода обхода дерева. Я надеюсь, что эта статья поможет вам освоить оба метода, понять принципиальные различия между ними и оптимально применить их для решения задач обхода дерева. Спасибо за ваше время :)