Leetcode: Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

Similar Problems:

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?


You may only use constant extra space.

For example,
Given the following binary tree,
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/populating-next-right-pointers-in-each-node-ii
## Basic Ideas: Process nodes: from top to down, left to right
##              How to process:
##                 p.left.next = p.right
##                 p.right = p.next.left
##              How to move to next node?
##                 p.next
##                 first: first node of next layer
## Complexity: Time O(n), Space O(1)
# 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:
        p = root
        first = p.left if root.left else root.right
        while p:
            # process p
            if p.left and p.right:
                p.left.next = p.right
                if p.next:
                    p.right.next = self.getNextRight(p)
            elif p.left:
                # only left sub-tree
                if p.next:
                    p.left.next = self.getNextRight(p)
            elif p.right:
                # only right sub-tree
                if p.next:
                    p.right.next = self.getNextRight(p)

            # move to next node
            if p.next:
                p = p.next
                p = first
                first = self.getNextFirst(first)

    def getNextFirst(self, p):
        while p and p.left is None and p.right is None:
            p = p.next
        if p is None:
            return None
            return p.left if p.left else p.right

    def getNextRight(self, p):  
        q = p.next
        while q:
            # process q
            if q.left or q.right:
                return q.left if q.left else q.right
            q = q.next
        return None

Share It, If You Like It.

Leave a Reply

Your email address will not be published.