117.Populating Next Right Pointers in Each Node II

Tags: [BFS], [queue], [level_by_level], [tree], [binary_tree], [list], [linked_list]

Com: {fb}

Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/#/description

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

Solution: Using Constant Space

# 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

from collections import deque

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

        curr = root
        while curr:
            head = None
            prev = None
            while curr:
                if not head:
                    if curr.left:
                        head = curr.left
                        prev = head
                        if curr.right:
                            prev.next = curr.right
                            prev = curr.right

                    elif curr.right:
                        head = curr.right
                        prev = head
                else:
                    if curr.left:
                        prev.next = curr.left
                        prev = curr.left
                    if curr.right:
                        prev.next = curr.right
                        prev = curr.right

                curr = curr.next

            curr = head

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(1).

Solution: BFS, Queue, Level By Level

# 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

from collections import deque

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

        queue = deque([root, None])
        prev = None
        while queue:
            curr = queue.popleft()
            if curr:
                if not prev:
                    if curr.left:
                        prev = curr.left

                        if curr.right:
                            prev.next = curr.right
                            prev = curr.right

                    elif curr.right:
                        prev = curr.right

                else:
                    # prev is not None
                    if curr.left:
                        prev.next = curr.left
                        prev = curr.left

                    if curr.right:
                        prev.next = curr.right
                        prev = curr.right

                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            else:
                # curr.next is None
                # here is the end of the current level
                prev = None

                if queue:
                    queue.append(None)

Revelation:

• Scan the tree level by level, when we visit each node, we try to link the nodes on its next level, which means we are always walking at current level, but linking the nodes on the next level, which also means the current level nodes have been linked.
• We should not use 'if curr.next' to detect here is the the end of the current level or not, because if we do that the current node will not be processed. So we still use None to detect here is the end of the current level or not.
• Using prev to chain all nodes together, if prev is None, it means the curr.left or curr.right will be the first node in this linked list.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(n), n is the number of nodes of the given tree.