117. Populating Next Right Pointers in Each Node II

Problem Statement

link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

Given a binary tree

struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#]

Input: root = [] Output: []

Solution Approach

The solution iteratively sets the next pointers of nodes on each level, starting from the root to the deepest level, by maintaining a pointer (cur) to traverse the current level and two pointers (head and pre) to help set up the next level.

Algorithm

1. Traverse the current level with cur pointer, setting next pointers for child nodes.
2. For each node, check left and right children, and link them using the pre pointer.
3. Once the current level is done, jump to the next level by setting cur to head.
4. Continue the process until all levels are traversed.

Implement

    class Solution:
  def connect(self, root: 'Node') -> 'Node':
      cur = root
      head, pre = None, None
      while cur:
          if cur.left:
              if pre:
                  pre.next = cur.left
              else:
                  head = cur.left
              pre = cur.left
          if cur.right:
              if pre:
                  pre.next = cur.right
              else:
                  head = cur.right
              pre = cur.right
          cur = cur.next
          if not cur:
              cur = head
              pre, head = None, None
      return root
       
 

    
    

Twitter  facebook  Email