Поиск в глубину - DFS

В глубоком обходе (Depth-first search - DFS) мы отдаем приоритет глубине, проходя как можно дальше вниз по дереву в одном направлении (до достижения листового узла), прежде чем рассматривать другое направление. Например, если мы выбираем левое направление в качестве приоритетного, то будем двигаться исключительно по node.left, пока левое поддерево не будет полностью исследовано. Затем мы исследуем правое поддерево.

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

Поскольку нам нужно возвращаться вверх по дереву после достижения конца ветви, DFS обычно реализуется с использованием рекурсии, хотя иногда это делается итеративно с использованием стека. Вот простой пример рекурсивного DFS для посещения каждого узла:

let dfs = (node) => {
  if (!node) {
    return;
  }

  dfs(node.left);
  dfs(node.right);
  return;
};

Структура выполнения DFS

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

1. Обработка базового случая(ев). Обычно пустое дерево (node = null) является базовым случаем.
2. Выполнение некоторой логики для текущего узла.
3. Рекурсивный вызов для детей текущего узла.
4. Возврат ответа.

Пункты 2 и 3 можно менять местами и это будет приводить к разному типу обхода дерева

Важные аспекты решения задач на бинарные деревья

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

Мы упомянули, что существует три типа глубинного обхода (DFS). Каждый из трех типов отличается только порядком выполнения шагов 2/3.

Имя каждого обхода описывает, когда выполняется логика текущего узла:

• Pre -> before children
• In -> in middle of children
• Post -> after children

Рассмотрим эти типы, используя следующее дерево в качестве примера:

Обход в прямом порядке (Preorder Traversal)

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

let preorderDfs = (node) => {
  if (!node) {
    return;
  }

  console.log(node.val);
  preorderDfs(node.left);
  preorderDfs(node.right);
  return;
};

Вывод - 0, 1, 3, 4, 6, 2, 5

Обход в симметричном порядке (Inorder Traversal)

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

let inorderDfs = (node) => {
  if (!node) {
    return;
  }

  inorderDfs(node.left);
  console.log(node.val);
  inorderDfs(node.right);
  return;
};

Вывод - 3, 1, 4, 6, 0, 2, 5

Обход в обратном порядке (Postorder Traversal)

При обходе в обратном порядке (postorder traversal) мы сначала рекурсивно вызываем детей, а затем выполняем логику для текущего узла. Это означает, что никакая логика не будет выполнена, пока мы не достигнем листового узла, так как вызов детей имеет приоритет над выполнением логики. В обходе в обратном порядке корневой узел — это последний узел, для которого выполняется логика.

let postorderDfs = (node) => {
  if (!node) {
    return;
  }

  postorderDfs(node.left);
  postorderDfs(node.right);
  console.log(node.val);
  return;
};

Вывод - 3, 6, 4, 1, 5, 2, 0

Задачи

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
https://leetcode.com/problems/path-sum/description/
https://leetcode.com/problems/count-good-nodes-in-binary-tree/
https://leetcode.com/problems/same-tree/
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/
https://leetcode.com/problems/diameter-of-binary-tree/description/