Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

117. Populating Next Right Pointers in Each Node II

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  Node* connect(Node* root) {
    Node* node = root;  // The node just above current needling

    while (node) {
      Node dummy(0);  // Dummy node before needling
      // Needle children of node
      for (Node* needle = &dummy; node; node = node->next) {
        if (node->left) {  // Needle left child
          needle->next = node->left;
          needle = needle->next;
        }
        if (node->right) {  // Needle right child
          needle->next = node->right;
          needle = needle->next;
        }
      }
      node = dummy.next;  // Move node to the next level
    }

    return root;
  }
};




			


class Solution {
  public Node connect(Node root) {
    Node node = root; // The node just above current needling

    while (node != null) {
      Node dummy = new Node(); // Dummy node before needling
      // Needle children of node
      for (Node needle = dummy; node != null; node = node.next) {
        if (node.left != null) { // Needle left child
          needle.next = node.left;
          needle = needle.next;
        }
        if (node.right != null) { // Needle right child
          needle.next = node.right;
          needle = needle.next;
        }
      }
      node = dummy.next; // Move node to the next level
    }

    return root;
  }
}




			


class Solution:
  def connect(self, root: 'Node') -> 'Node':
    node = root  # The node just above current needling

    while node:
      dummy = Node(0)  # Dummy node before needling
      # Needle children of node
      needle = dummy
      while node:
        if node.left:  # Needle left child
          needle.next = node.left
          needle = needle.next
        if node.right:  # Needle right child
          needle.next = node.right
          needle = needle.next
        node = node.next
      node = dummy.next  # Move node to the next level

    return root