Leetcode 117: Populating Next Right Pointers in Each Node II

         1
       /  \
      2    3
     / \    \
    4   5    7

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Code 

from collections import deque
# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return

        d = deque([(root, 0)])
        
        while d:
            if len(d) >= 2:
                # level is the same
                if d[0][1] == d[1][1]:
                    d[0][0].next = d[1][0]
                
            old_node, old_lvl = d.popleft()
            if old_node.left: d.append((old_node.left, old_lvl + 1))
            if old_node.right: d.append((old_node.right, old_lvl + 1))

Idea

Using BFS. Also look at the similar problem: https//nb4799.neu.edu/wordpress/?p=2044. Time complexity and space complexity are both O(N).

Code

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    
    def find_child(self, node, start_from_left_or_right):
        """ find the first occurrence of a child from the level of node.

        Return:
        1. child node
        2. its parent node
        3. "left" if it is the left child of its parent, otherwise "right"

        If child node is not found, return (None, None, None)
        """
        
        if node and start_from_left_or_right == 'right':
            if node.right:
                return node.right, node, 'right'
            else:
                node = node.next

        while node:
            if node.left:
                return node.left, node, 'left'
            elif node.right:
                return node.right, node, 'right'
            else:
                node = node.next

        return None, None, None


    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None: 
            return
        
        # pre is the first node in the previous layer
        pre = root
        
        while pre:
            # search the first child in the current layer
            first_child, first_child_parent, first_child_as_left_or_right = self.find_child(pre, 'left')
            pre = first_child

            while first_child is not None:
                # search the next child in the current layer
                if first_child_as_left_or_right == "left":
                    second_child, second_child_parent, second_child_as_left_or_right = \
                        self.find_child(first_child_parent, 'right')
                else:
                    second_child, second_child_parent, second_child_as_left_or_right = \
                        self.find_child(first_child_parent.next, 'left')
                
                if second_child is not None:
                    first_child.next = second_child
                    
                first_child, first_child_parent, first_child_as_left_or_right = \
                    second_child, second_child_parent, second_child_as_left_or_right                 



            
                

Idea

Modified from the O(1) space solution from: https//nb4799.neu.edu/wordpress/?p=2044