moonlightshadow123
6/22/2017 - 7:28 AM

117. Populating Next Right Pointers in Each Node II

  1. Populating Next Right Pointers in Each Node II
solution.py
content_copyfile_download
# For our current solution, it doesn't matter if the tree is perfect or not.

# 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 == None:
            return
        queue = [root]
        while len(queue) != 0:
            levelNum = len(queue)
            prev = None
            for i in range(levelNum):
                curNode = queue[0]
                del queue[0]
                curNode.next = prev
                prev = curNode
                if curNode.right:
                    queue.append(curNode.right)
                if curNode.left:
                    queue.append(curNode.left)
117-Populating-Next-Right-Pointers-in-Each-Node-II.md
content_copyfile_download
  • Rendered
  • Source

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