Bit longer but very intuitive solution using level by level traversal - Python


  • 0
    C

    The idea is very simple, without reinventing the wheel -
    Traverse level by level and keep track of the items in a list.
    Once you're at the end of a level, link the next pointers from left to right.

    class Solution:
        # @param root, a tree link node
        # @return nothing
        def connect(self, root):
            if not root:
                return
            queue = collections.deque()
            queue.appendleft(root)
            queue.appendleft('#')
            curr_list = []
            while len(queue) > 0:
                curr = queue.pop()
                if curr == '#':
                    if len(queue) > 0:
                        queue.appendleft('#')
                        count = 1
                        while count < len(curr_list):
                            curr_list[count-1].next = curr_list[count]
                            count += 1
                        curr_list[-1].next = None
                        curr_list = []
                        continue
                else:
                    if curr.left:
                        curr_list.append(curr.left)
                        queue.appendleft(curr.left)
                    if curr.right:
                        curr_list.append(curr.right)
                        queue.appendleft(curr.right)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.