Simple Python recursive solution


  • 1
    C
    class Solution:
        # @param root, a tree link node
        # @return nothing
        def connect(self, root):
            if not root or not root.left:
                return
            root.left.next = root.right
            if root.next:
            	root.right.next = root.next.left
            self.connect(root.left)
            self.connect(root.right)

  • 0

    I doubt that the recursion only uses constant extra space.


  • 0
    C

    I store nothing on the stack. I only change the value of pointers, right?


  • 0

    Even just the managing of recursion costs memory proportional to the recursion depth. And you do explicitly add to the stack with the root argument. Every recursive call has its own root reference. And they have to be remembered somewhere.


  • 0
    C

    Correct. Great explanation!


  • 0
    C

    Recursive Python solution while space is not constant:

    def connect(self, root):
        if root and root.left and root.right:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
            self.connect(root.left)
            self.connect(root.right)
    

Log in to reply
 

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