algorithm - 将每个叶子节点的右指针更改为二叉树中的下一个叶子节点

Question

最近我在互联网上看到一个问题，想知道是否有比我所做的更有效的解决方案。

队列:将每个叶节点的右指针更改为二叉树中的下一个叶节点。
叶子可能不在同一水平。

二叉树的节点的形式为:

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)。