Связывание узла на ту же глубину в бинарном дереве

Вам даются класс NodeСвязывание узла на ту же глубину в бинарном дереве

public class Node { 
    Node left; 
    Node right; 
    Node next; 
}

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

И вы не должны использовать линейное количество дополнительной памяти, например, аннотирование каждого узла своей глубиной. Это означает, что нет дополнительного поля, такого как int depth в классе Node или аналогичных намерений, таких как карта Map<Node, Integer>.

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

Однако интервьюер попросил меня НЕ комментировать глубину каждого узла. Пожалуйста, помогите мне решить эту проблему. Благодарю. И, пожалуйста, скажите, работает ли время работы O(n) для решения без аннотаций.

источник

2015-04-05 InformedA

Является ли причина того, что вы не можете обменивать узлы или нажимать для решения сублинейного пространства? Это можно сделать без анотации, удерживая две очереди в BFS, одну для текущей глубины и одну для следующей глубины, и переключаться между ними, когда один из них исчерпан, - но это остается O (n) пространством с O (n) временем. – amit

Другим вариантом с O (h) пространством и временем O (n^2) является [IDDFS] (http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) – amit

@amit 'O (n^2)' is ужасное решение, в то время как мы можем иметь «O (n)» с линейным объемом памяти для аннотации глубины. Вы знаете лучшее решение? – InformedA

Я предполагаю, что вы знаете высоту дерева h (может быть рассчитано в O(n) времени и пространстве журнала). Поддерживая список хвостов для всех списков h, вы можете использовать DFS для генерации списков. Вам нужно будет только хранить h хвостовые элементы и параметры стека вызовов (O(log n) дополнительное пространство):

Initialize:

listTails := array with h null entries (type Node) 
n := root 
depth := 0

И называют:

function buildLists(Node n, int depth, Node[] listTails) 
{ 
    if(n == null) 
     return; 

    if(listTails[depth] != null) 
     listTails[depth].next = n; 
    listTails[depth] = n; 

    buildLists(n.left, depth + 1, listTails); 
    buildLists(n.right, depth + 1, listTails); 
}

Если вы используете динамический-размер хранилище данных для хвостов списка (например, std::vector<> на C++), даже не нужно знать h.

Это по существу распространяет фронт слева направо по всему дереву.

источник

2015-04-05 17:25:15

Это то, что я думаю, это то, что он ищет. Неплохо. – InformedA

Связывание узла на ту же глубину в бинарном дереве

ответ

Смежные вопросы