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?

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

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:
            return
        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
            else:
                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
        else:
            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
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.