Найти все пары последовательных номеров в BST

Question

Мне нужно написать код, который найдет все пары последовательных номеров в BST.

Например: возьмем BST T с ключом 9, T.left.key = 8, T.right.key = 19. Существует только одна пара - (8, 9).

Наивное решение, о котором я думал, состоит в том, чтобы сделать любой обход (pre, in, post) в BST и для каждого узла, чтобы найти его преемника и предшественника, и если один или два из них являются последовательными к узлу - мы их распечатаем. Но проблема в том, что он будет O (n^2), потому что у нас есть n узлов, и для каждого из них мы используем функцию, которая принимает O (h), что в худшем случае h ~ n ,

Второе решение - скопировать все элементы в массив и найти последовательные числа в массиве. Здесь мы используем O (n) дополнительное пространство, но время работы лучше - O (n).

Вы можете помочь мне найти эффективный алгоритм для этого? Я пытаюсь думать об алгоритме, который не использует дополнительное пространство, а его время работы лучше, чем O (n^2)

* Требуемый вывод - это число этих пар (нет необходимости печатать пар).

* любые 2 последовательных целых числа в BST представляют собой пару.

* BST содержит только целые числа.

Спасибо!

Answer 1

Почему вы просто не совершаете обходные и подсчетные пары на лету? Вам понадобится глобальная переменная, чтобы отслеживать последний номер, и вам нужно будет инициализировать ее до , а не, что меньше первого числа (например, корень дерева). Я имею в виду:

// Last item 
int last; 

// Recursive function for in-order traversal 
int countPairs (whichever_type treeRoot) 
{ 
    int r = 0; // Return value 

    if (treeRoot.leftChild != null) 
    r = r + countPairs (treeRoot.leftChild); 

    if (treeRoot.value == last + 1) 
    r = r + 1; 

    last = treeRoot.value; 

    if (treeRoot.rightChild != null) 
    r = r + countPairs (treeRoot.rightChild); 

    return r; // Edit 2016-03-02: This line was missing 
} 

// Main function 
main (whichever_type treeRoot) 
{ 
    int r; 

    if (treeRoot == null) 
    r = 0; 
    else 
    { 
    last = treeRoot.value; // to make sure this is not one less than the lowest element 
    r = countPairs (treeRoot); 
    } 

    // Done. Now the variable r contains the result 
}