Изменить правый указатель каждого листового узла на следующий листовой узел в двоичном дереве

Question

Недавно я увидел вопрос в Интернете и хочу знать, есть ли более эффективное решение, чем то, что я сделал.

Queus: изменить правый указатель каждого листового узла на следующий листовой узел в двоичном дереве.
Листья могут быть не на одном уровне.

узел бинарного дерева имеет форму:

struct node 
{ 
    struct node *left , *right ; 
    int key; 
}; 

Я решил его с помощью LEVEL ORDER TAVERSAL (BFS) на дереве и, наконец, получили все узлы листьев в очереди.
Теперь соединительные узлы очень легко:

while(queue is not empty) 
{ 
    currentnode = queue.pop(); 
currentnode->right= queue.top(); 
} 
currentnode->right= NULL;// queue becomes empty on taking out last node 

я использую O (N) времени, но дополнительное пространство O (N). можно ли сделать, не занимая меньше места или места?

Answer 1

Я бы предложил следующий подход, конечно, он должен быть протестирован, но я думаю, что он должен работать.

Если вы выполните Обратный порядок бинарного дерева, вы найдете узлы в левом порядке. Теперь мы можем проверить, если узел является листом, и если это лист, мы должны сделать две вещи:

1. link the previous leaf to current leaf 
2. update the current leaf as the previous 

---

void inOrderTraversal(Node root, Node previous){ 
    if(root!=null){ 
     inOrderTraversal(root.left, previous); 
     if(root.left==null && root.right==null){ 
     if(previous!=null) 
      previous.right=root; 
     previous=root; 
     } 
     inOrderTraversal(root.right, previous); 
    } 
} 

Таким образом, у вас есть лучшее пространство сложность: O (1).

Answer 2

В своем алгоритме вместо хранения листьев в очереди просто делайте правильные указатели предыдущей точки листа на текущий лист, когда идете.

lastLeaf->right = currLeaf; 
lastLeaf = currLeaf;