Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Connect Level Order Siblings

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

{
   std::queue<TreeNode*> nodes;

    nodes.push(root);
    while(!nodes.empty())
    {
      std::queue<TreeNode*> nodesInLevel; // <- this one
      auto level = nodes.size();
      for(auto i = 0; i < level; ++i)
      {
        auto node = nodes.front();
        nodes.pop();
        nodesInLevel.push(node);

        if(node->left)
          nodes.push(node->left);

        if(node->right)
          nodes.push(node->right);
      }

      while(!nodesInLevel.empty())
      {
        auto prev = nodesInLevel.front();
        nodesInLevel.pop();

        if(!nodesInLevel.empty())
        {

          auto curr = nodesInLevel.front();
          prev->next = curr;

        }
      }
    }

    return root;
}
//It still has generally O(n) space complexity but simplified from O(n/2 +
A

Anonymous

· 3 years ago

All the previous Tree BFS Level Order Examples are returning something, why aren't we doing it here? Is it inherent that the tree is being returned?

Also why does this one include the print function but previous versions don't? This makes it so you don't see the input and output when the Solution is Executed.

from __future__ import print_function
from collections import deque


class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right, self.next = None, None, None

  # level order traversal using 'next' pointer
  def print_level_order(self):
    nextLevelRoot = self
    while nextLevelRoot:
      current = nextLevelRoot
      nextLevelRoot = None
      while current:
        print(str(current.val) + " ", end='')
        if not nextLevelRoot
A

Anonymous

· 4 years ago

// levelSize static void connect(TreeNode *root) { if (!root) return;

queue nodes_queue; nodes_queue.push(root);

while(!nodes_queue.empty()) { int levelSize = nodes_queue.size();

while(levelSize--) { TreeNode* current = nodes_queue.front();

if(current->left) nodes_queue.push(current->left); if(current->right) nodes_queue.push(current->right);

if(!levelSize) { // 0 current->next = NULL; nodes_queue.pop(); break; }

nodes_queue.pop();

current->next = nodes_queue.front(); } } }

A

Anonymous

· 5 years ago

public TreeNode connect(TreeNode root) {

if (root == null) { return root; }

// Start with the root node. There are no next pointers // that need to be set up on the first level Node leftmost = root;

// Once we reach the final level, we are done while (leftmost.left != null) {

// Iterate the "linked list" starting from the head // node and using the next pointers, establish the // corresponding links for the next level Node head = leftmost;

while (head != null) {

// CONNECTION 1 head.left.next = head.right;

// CONNECTION 2 if (head.next != null) { head.right.next = head.next.left; }

// Progress along the list (nodes on the current level) head = head.next; }

// Move onto the next level leftmost = leftmost.left; }

return root; }

This is a solution with O(1) space.

Show 2 replies

Reading Progress

0%

Vote for new content