Можете ли вы перевернуть binary tree по вертикальной оси? Это известная проблема, ставшая популярной благодаря этому твиту:

Google: 90% наших инженеров используют написанное вами программное обеспечение (Homebrew), но вы не можете инвертировать двоичное дерево на доске, так что отвали.

- Макс Хауэлл (@mxcl) 10 июня 2015 г.

Учитывая такой binary tree:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Выполнение инверсии приведет к:

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Определение узла дерева следующее:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

Изначально этот урок был опубликован на https://algodaily.com, где я веду курс технических собеседований и пишу аналитические статьи для амбициозных разработчиков.

Это знаменитый вопрос, который Homebrew автор Max Howell классно ошибся в интервью Google. Надеюсь, это избавит вас от такого же несчастья!

Давайте подумаем о грубой силе - как бы мы это сделали без каких-либо хитроумных алгоритмов? Мы можем начать с очень простого ввода следующим образом:

  1
 / \
2   3

Итак, чтобы перевернуть его по вертикали, мы начнем с 1, где нечего переворачивать или менять местами, и он останется на месте. Мы обработали первую строку.

Переходя ко второму, мы встречаем 2 и 3, так что мы поменяли их местами и получили:

  1
 / \
3   2

Интересно, похоже, это перевернуло его! Неужели это так же просто, как замена местами, когда узлов больше одного?

Что, если бы у нас было более двух узлов для обмена на каждом уровне? Если бы был дополнительный уровень, он мог бы выглядеть так:

      1
     / \
    3   2
   / \   \
  4   5   3

Эта последняя строка в настоящее время направлена ​​4 -> 5 -> 3, но мы бы хотели, чтобы результат был 3 -> 5 -> 4, чтобы правильно инвертировать.

Однако мы можем добиться этого, выполнив две отдельные перестановки. Обратите внимание: это то, что мы получили бы, если поменяли местами 4 и 5, чтобы получить 5 -> 4, а затем поменяли местами 5 -> 4 на 3.

      1
     / \
    2   3
   /   / \
  3   5   4

Итак, чтобы собрать все вместе: мы можем выполнять обход по порядку и делать своп на каждой итерации.

Предостережение, на которое указали читатели: если мы имеем дело с существенно большим двоичным деревом, то рекурсивное решение может вызвать проблемы из-за размера стека вызовов. Есть два способа обойти это:

  1. Использование стека для имитации рекурсии
  2. Используя очередь, посещая уровни один за другим в режиме BFS и меняя местами левый и правый узлы, чтобы инвертировать дерево.

Вот как выглядит окончательный код:

function invertTree(head) {
  if (head) {
    var temp = head.left;
    head.left = head.right;
    head.right = temp;

    invertTree(head.left);
    invertTree(head.right);
  }

  return head;
}

Первоначально опубликовано на https://algodaily.com.