Можете ли вы перевернуть 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
Итак, чтобы собрать все вместе: мы можем выполнять обход по порядку и делать своп на каждой итерации.
Предостережение, на которое указали читатели: если мы имеем дело с существенно большим двоичным деревом, то рекурсивное решение может вызвать проблемы из-за размера стека вызовов. Есть два способа обойти это:
- Использование стека для имитации рекурсии
- Используя очередь, посещая уровни один за другим в режиме 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.