1 minute read

117. Populating Next Right Pointers in Each Node II

Difficulty: Medium

Related Topics: Linked List, Tree, BFS/DFS, Binary Tree

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 1:

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.

Example 2:

Input: root = [] Output: []

Code:

# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

from collections import deque

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        def bfs(root):
            myqueue = deque()
            myqueue.append((root,0))
            tmp = (Node(),0)
            while len(myqueue) != 0:
                count = len(myqueue)
                if count == 1:
                    curr = myqueue.popleft()
                    if curr[0] != None:
                        if curr[0].left and curr[0].right:
                                curr[0].left.next = curr[0].right
                        if curr[0].left:                              
                            myqueue.append((curr[0].left,curr[1]+1))
                        if curr[0].right:
                            myqueue.append((curr[0].right,curr[1]+1))
                else:
                    for i in range(1,count+1):
                        curr = myqueue.popleft()
                        if curr[0] != None:
                            if curr[0].left and curr[0].right:
                                curr[0].left.next = curr[0].right
                            if count == 2**curr[1]:                           
                                if i%2==0 and i!=count:
                                    tmp = curr
                                if i%2==1 and tmp[1]==curr[1]:
                                    tmp[0].next = curr[0]
                            if count != 2**curr[1]:
                                if i == 1:
                                    tmp = curr
                                if i != 1:
                                    tmp[0].next = curr[0]
                                tmp = curr
                        if curr[0].left:                              
                            myqueue.append((curr[0].left,curr[1]+1))
                        if curr[0].right:
                            myqueue.append((curr[0].right,curr[1]+1))
            return root
        return bfs(root)

Feedbacks:

From the previous leetcode problem No. 116, I added few lines to solve this problem. Since the tree from this problem is not a perfect binary tree, I only need to consider cases when parent node only has one or no child node. On the same level of traverse, if total node in that level is not same as 2**level means that there is at least one small tree that is not perfect. So, I only needed to modifiy codes for that kind of nodes.

You may also enjoy