Boundary Traversal of Binary Tree
Массив root хранит двоичное дерево в порядке уровней: корень находится по индексу 0, дети узла с индексом i — по индексам 2i+1 (левый) и 2i+2 (правый), -1 обозначает пустое место, а в конце могут быть дополнительные элементы -1. Лист — это узел без детей.
Верните границу против часовой стрелки, начиная с корня:
- Корень.
- Левая граница сверху вниз: начиная с левого ребёнка корня, переходите к левому ребёнку, если он есть, иначе — к правому. Остановитесь перед листом.
- Все листья слева направо.
- Правая граница снизу вверх: зеркальное отражение левой границы, начиная с правого ребёнка корня.
Ни один узел не указывается дважды, поэтому дерево из одного узла содержит только корень.
Функция
- rootinteger-array
- двоичное дерево в порядке уровней, где -1 обозначает пустое место
- Возвращаетinteger-array
- граничные значения, против часовой стрелки от корня
Ограничения
1 ≤ root.length ≤ 32767- Каждый элемент
root[i]равен-1или является значением, для которого0 ≤ root[i] ≤ 105. root[0]никогда не равно-1, поэтому в дереве есть как минимум один узел.- Массив может оканчиваться дополнительными элементами
-1, расположенными после последнего узла. - Оба потомка пустого места тоже пусты, а глубина не превышает
14. - Значения узлов различны.
Примеры
- Ввод
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Вывод
- [7, 3, 1, 4, 6, 8, 9]
- Пояснение
- После корневого узла
7левая граница —3: его дочерний узел1— лист. Листья —1,4,6,8. Правая граница —9, над листом8.
- Ввод
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Вывод
- [10, 4, 6, 5, 8]
- Пояснение
- У
4нет левого потомка, поэтому левая граница переходит к6, а затем останавливается на листе5. Далее идут листья5,8. У корня нет правого потомка.
- Ввод
- root = [3]
- Вывод
- [3]
- Пояснение
- Корень — это всё дерево. Он указан один раз, а не повторно как лист.
Дополнительный вопрос
Как бы ты перечислил границу по часовой стрелке: корень, правый край сверху вниз, листья справа налево, затем левый край снизу вверх?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Раздели ответ на четыре части: корень, левый край, листья, правый край. Какие из них представляют собой один путь вниз по дереву, а для каких нужен полный обход?
Каждое ребро — это путь: от дочернего узла корня продолжай двигаться к дочернему узлу с этой стороны или к другому дочернему узлу, если с этой стороны узла нет. Листья в порядке слева направо получаются при обходе в глубину, который сначала посещает левое поддерево. Обрати внимание на соединения: лист, в котором заканчивается ребро, входит в число листьев.
Пройдите вниз, начиная с индекса
1, и добавьте каждый нелистовой узел. Затем добавьте каждый листовой узел, обходя дерево в прямом порядке. Затем пройдите вниз, начиная с индекса2, соберите каждый нелистовой узел и добавьте этот список в обратном порядке.
Решение
Ответ объединяет четыре части: корень, путь вниз по левому краю, листья слева направо и путь вниз по правому краю, прочитанный в обратном порядке. В местах соединения лист, завершающий край, и корень, являющийся листом, должны быть перечислены по одному разу.
Пройдите три части отдельно
Идея
Каждое ребро представляет собой один путь: от дочернего узла корня перечисляйте узлы, пока следующий узел не станет листом, который вместо этого перечисляется в части для листьев. Обход в прямом порядке, при котором сначала посещается левое поддерево, а затем правое, встречает листья слева направо, потому что каждый узел левого поддерева находится левее правого поддерева независимо от его глубины. Соберите правое ребро сверху вниз и добавьте его в обратном порядке.
Каждое ребро проходит по одному пути, а обход листьев посещает каждый узел один раз: время O(n), рекурсия достигает глубины h уровней.
Алгоритм
- Начните с корня; если это лист, верните его.
- Начиная с индекса
1, пока узел существует и не является листом, добавляйте его и переходите к его левому потомку или к правому, если левого нет. - Выполните обход в прямом порядке, сначала слева, начиная с индексов
1и2, добавляя каждый лист. - Начиная с индекса
2, выполните то же, что и в шаге 2, отдавая предпочтение правым потомкам и собирая узлы. - Добавьте собранные узлы в обратном порядке.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultОдин обход в прямом порядке с флагами рёбер
Идея
Объедини обходы в один прямой обход со стеком, присвоив каждому узлу флаг: 1 на левом краю, 2 на правом краю, 0 внутри. Потомки корня начинают с 1 и 2. Узел на краю передаёт свой флаг потомку со своей стороны или своему единственному потомку; все остальные потомки получают 0. Во втором примере 1 передаётся от 4 к 6, а затем к 5.
Когда узлы снимаются со стека, добавляй каждый лист и каждый внутренний узел с флагом 1; внутренние узлы с флагом 2 собирай отдельно и добавляй в обратном порядке в конце. При прямом обходе каждый узел левого края достигается раньше любого листа, потому что край поворачивает направо только там, где слева от него ничего нет.
Алгоритм
- Начни с корня. Помести его правого потомка в стек с флагом
2, затем левого потомка с флагом1. - Извлеки узел из стека. Добавь его, если он является листом или имеет флаг
1; нелистовой узел с флагом2добавь в правый список. - Помести его правого потомка в стек, затем левого потомка, каждому присвоив флаг согласно правилу.
- Когда стек опустеет, добавь элементы правого списка в обратном порядке.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Ловушки и крайние случаи
- Перечисление узла дважды. Обход ребер, который не останавливается перед листом, перечисляет
1дважды в примере 1, а дерево из одного узла не должно повторно перечислять корень как лист. - Выбор первого узла каждого уровня в качестве левой границы. Если левый потомок корня — лист, а правая подветвь глубже, то на более глубоких уровнях первыми будут узлы правой подветви, но левая граница будет пустой.
- Переход только по левым потомкам. В примере 2 граница должна идти от
4к его правому потомку6. - Сбор листьев по уровням. Тогда в примере 1 получится
1,8,4,6. - В Lua и R оставляйте индексы узлов нулевыми для арифметики
2i+1и считывайтеroot[i + 1].
Частые вопросы3
Что такое обход границы бинарного дерева?
Он перечисляет контур дерева против часовой стрелки: корень, левый край сверху вниз, листья слева направо и правый край снизу вверх. Края не включают листья, поэтому ни один узел не появляется дважды.
Какова временная сложность обхода границы?
O(n). Каждый из двух обходов по границе следует по одному пути, а обход листьев посещает каждый узел один раз. Дополнительная память составляет O(h) для рекурсии или стека.
Левая граница всегда следует за левыми потомками?
Нет. Он переходит к левому потомку, если он есть, а в противном случае — к правому потомку: это самый внешний путь, который виден слева. Если у корня нет левого потомка, левая граница пуста.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def boundaryTraversal(root):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Ожидаемый вывод
[7, 3, 1, 4, 6, 8, 9]