Given the root of a binary search tree, link all the nodes at the same level, by using an additional Node* level.

Question

Sigiloso · Accepted Answer

Start from the root, 
put all the nodes in a queue,
keep track of number of nodes at current level and at next level by counting,
dequeue a node from the queue, 
put its left and right children in the queue by updating your counts,
using your counts, connect the nodes at the same level.
O(N) in both time and space.

redgiant · Answer

Queue size is never larger than half+1 of the node count, just noting. Rough code:

Queue q = new Queue();
q.Enqueue(root);

int count = 1;
int nextCount = 0;
T prev = null;

while (!q.Empty())
{
  T cur = q.Dequeue();

  if (prev != null)
  {
    // doubly-link level siblings
    prev.rightSibling = cur;
    cur.leftSibling = prev;
  }

  count--;

  if (count == 0)
  {
    // next level
    count = nextCount;
    nextCount = 0;
    prev = null;
  }
  else
  {
    // same level
    prev = cur;
  }

  if (cur.Left != null)
  {
    nextCount++;
    q.Enqueue(cur.Left);
  }

  if (cur.Right != null)
  {
    nextCount++;
    q.Enqueue(cur.Right);
  }
}

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas