Найдите два числа в дереве двоичного поиска, которые составляют в целом третье число
Вы могли использовать отражение, чтобы получить все свойства объекта, чем цикл через него, и получить значение свойства, где имя (свойства) соответствует переданному в параметре.
1 ответ
Как я мог, я не уверен, что это возможно с бинарным деревом, не имеющим родительских указателей. O (1) пробел означает, что вы не можете ни использовать рекурсию (рост стека составляет O (log n) ), ни копировать в двусвязный список ( O (n) ).
Метод, который вы ссылаетесь на , представляет собой решение временной сложности O (n) , но не с обычным двоичным деревом. Фактически, я подробно ответил на аналогичный вопрос здесь . Это было решено с помощью пробела O (n) , но только потому, что они изначально не были отсортированы.
Это возможно с деревом, содержащим родительские указатели. Если дочерние узлы имеют указатели на своих родителей, вы можете в основном рассматривать дерево как двусвязный список, обрабатываемый итеративно.
Для этого, вы перемещаете указатель начала вниз к самому левому узлу, а указатель конца вниз к самому правому узлу. Вы также поддерживаете две переменные для хранения последнего движения (вверх или поперек, первоначально вверх) каждого указателя, чтобы вы могли разумно выбрать следующий ход ( front ++ и end - в вашем вопрос).
Затем вы можете использовать текущие указатели и последние перемещения вместе с текущей суммой, чтобы решить, какой указатель перемещать (и как).