Интервью Q: Двоичное дерево Обход по порядку

Question

Мне задали этот вопрос в интервью.

Проблема:бинарного дерево и высота соответствующего поддерева также даны нам. Затем мы должны найти элемент в определенном положении по-порядку.

Например: Структура дерева является: D (корневой узел) [поддерево размер = 6] ->B, F (дочерние узлы D) [поддерево размер = 2] - >A, C, E, G (узлы листа) [размер поддерева = 0].

Таким образом, общая сумма 3 уровней: Level 0: D; Уровень 1: B, F; Уровень 2: А, С, Е, G

Мы должны Расчитать узел в определенном порядке/позиции в заказовМой, скажем, с. если p = 2, то узел будет B (по общему порядку).

Мое решение: Я предположил, что нам нужно сделать обход по порядку один раз (через BFS/DFS), а затем мы можем дать узел i-го порядка, а сложность времени будет O (n).

Теперь меня попросили, чтобы можно улучшить решение, основанное на информации о размере древовидного дерева. Но я не могу придумать, каким образом размер поддерева может уменьшить временную сложность.

Может ли информация о размере поддерева уменьшить временную сложность? Если да, то, пожалуйста, поделитесь алгоритмом/псевдокодом.

Answer 1

Если мы хотим, чтобы найти элемент в я-й позиции в заказовМои обходе:

• Мы знаем, что мы ищем корень, если левое поддерево имеет ровно i-1 узлов.
• Мы знаем, что это будет в левом поддереве, если левое поддерево имеет i или больше узлов.
• Мы знаем, что это будет в правом поддереве, если левое поддерево имеет менее i-1 узлов.
• Мы можем повторить это рекурсивно, соответствующим образом обновив i. Более конкретно, нам нужно уменьшить i на размер левого поддерева плюс один раз, когда мы переходим к правому поддереву, так как обход этого поддерева начинается в этом месте исходного обходного пути. Мы не должны менять i при переходе к левому поддереву, так как обход этого поддерева начинается в исходном положении исходного обходного пути.

Таким образом, в псевдо-коде, мы можем сделать следующее:

currentNode = root 
while true 
    if getSubtreeCount(currentNode.left) == i-1 
    return currentNode 
    else if getSubtreeCount(currentNode.left) < i-1 
    currentNode = currentNode.left 
    else 
    currentNode = currentNode.right 
    i -= getSubtreeCount(currentNode.left) + 1 

Это даст нам время работы O(treeHeight).

Пример:

Скажем, у нас есть дерево:

 D 
/ \ 
    B  F 
/\ /\ 
A C E G 

сказать, что мы ищем 2-ю позицию в заказовМои обходе. Мы начнем с D. Мы увидим, что левое поддерево имеет 3 узла, поэтому мы знаем, что вторая позиция находится в левом поддереве. Глядя на B, мы видим, что левое поддерево имеет 1 узел, поэтому мы знаем, что B находится во 2-й позиции.

Скажем, мы ищем пятую позицию в обходном пути. Мы начнем с D. Мы увидим, что левое поддерево имеет 3 узла, поэтому мы знаем, что 6-я позиция находится в правом поддереве. Глядя на F, мы теперь ищем 1-ю позицию, так как есть 4 узла в обходном пути, прежде чем мы перейдем к поддереву с F в качестве корня. Мы видим, что левое поддерево имеет 1 узел, поэтому мы знаем, что поддерево содержит узел в первой позиции. Глядя на E, мы видим, что левое поддерево имеет 0 узлов, поэтому мы знаем, что E находится в 1-й позиции в этом поддереве, то есть в узле, который мы ищем.