A Python Solution with O(1) space complexity and simply explain


  • 0
    A

    An easy understood version with O(n) space complexity.

    class Solution(object):
        def connect(self, root):
            """
            :type root: TreeLinkNode
            :rtype: nothing
            """
            if root is None:
                return
            stack = [root]
            while len(stack) is not 0:
                length = len(stack)
                for i in xrange(0, length-1):
                    stack[i].next = stack[i+1]
                nextStack = []
                for node in stack:
                    if node.left != None:
                        nextStack.append(node.left)
                    if node.right != None:
                        nextStack.append(node.right)
                stack = nextStack
            return
    

    The space complexity of following code is O(1), which connects node level by level.
    Actually the two code connecting nodes in same order, and the following code traversing the nodes on the next level by next pointer while the code above use stack to save the nodes in next level to traversal.

    class Solution(object):
        def connect(self, root):
            """
            :type root: TreeLinkNode
            :rtype: nothing
            """
            if root is None:
                return
            while root is not None:
                while root != None and root.left is None and root.right is None:
                    root = root.next
                if root == None:    return
                if root.left != None:
                    root.left.next = root.right
                pre = root.left
                if root.right != None:
                    pre = root.right
                nextNode = root.next
                while nextNode != None:
                    if nextNode.left != None:
                        nextNode.left.next = nextNode.right
                        pre.next = nextNode.left
                        pre = nextNode.left
                        if nextNode.right != None:
                            pre = nextNode.right
                    elif nextNode.right != None:
                        pre.next = nextNode.right
                        pre = nextNode.right
                    nextNode = nextNode.next
                if root.left != None:
                    root = root.left
                else:
                    root = root.right
            return

Log in to reply
 

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