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

LeetCode Solutions

116. Populating Next Right Pointers in Each Node

Time: $O(n)$

Space: $O(h)$

			


class Solution {
 public:
  Node* connect(Node* root) {
    if (root == nullptr)
      return nullptr;
    connectTwoNodes(root->left, root->right);
    return root;
  }

 private:
  void connectTwoNodes(Node* p, Node* q) {
    if (p == nullptr)
      return;
    p->next = q;
    connectTwoNodes(p->left, p->right);
    connectTwoNodes(q->left, q->right);
    connectTwoNodes(p->right, q->left);
  }
};




			


class Solution {
  public Node connect(Node root) {
    if (root == null)
      return null;
    connectTwoNodes(root.left, root.right);
    return root;
  }

  private void connectTwoNodes(Node p, Node q) {
    if (p == null)
      return;
    p.next = q;
    connectTwoNodes(p.left, p.right);
    connectTwoNodes(q.left, q.right);
    connectTwoNodes(p.right, q.left);
  }
}




			


class Solution:
  def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
    if not root:
      return None

    def connectTwoNodes(p, q) -> None:
      if not p:
        return
      p.next = q
      connectTwoNodes(p.left, p.right)
      connectTwoNodes(q.left, q.right)
      connectTwoNodes(p.right, q.left)

    connectTwoNodes(root.left, root.right)
    return root