3-4 lines Python


  • 52
    def invertTree(self, root):
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
    

    Maybe make it four lines for better readability:

    def invertTree(self, root):
        if root:
            invert = self.invertTree
            root.left, root.right = invert(root.right), invert(root.left)
            return root
    

    And an iterative version using my own stack:

    def invertTree(self, root):
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack += node.left, node.right
        return root

  • 1
    S

    Hi, StefanPochmann! I have learned a lot from your solution!


  • 0
    S

    I try to change your second version to the following one, but it always has error:
    if root:
    invert = self.invertTree
    root.left = invert(root.right)
    root.right = invert(root.left)
    return root


  • 4

    If you do root.left = invert(root.right) first, then you lost the previous left subtree. Of course that can't work. Also, please format multi-line code properly, especially Python code, which depends on indentation.


  • 1
    S

    Thanks a lot! I will pay attention for the format! Now I know how to swap two variables in place by python!


  • 0

    Hi, Stefan. Your solution to tree-related problems is always concise and elegant :-)


  • 0

  • 0
    A

    Hi, Stefan. I'm quite confused about the space complexity of the recursive method. Is it O(height) or O(number of total nodes)? Thanks.


  • 0

    @amyshang77 Yes, it's both of those.


  • 0
    U

    Hi Stefan, can you explain how is it both of those? Aren't both of them different?


  • 0
    X

    @StefanPochmann Hi stefan, i am really confused about the recursive in binary tree. Could you please give me some links or advice to learn this?
    i can not even understand how each line works> <


  • 1

    similar iterative solution:

        def invertTree(self, root):
            p = root
            stack = []
            while stack or root:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    root = stack.pop()
                    root.left, root.right = root.right, root.left
                    root = root.left
            return p
    

  • 1
    D

    @hotea,

    Interesting. Your iterative solution is iterative in-order DFS, and @StefanPochmann 's version is iterative pre-order DFS, while I first thought about iterative post-order DFS as an attempt of direct translation of the short recursive post-order. Apparently, all three versions work for this problem. In the recursive world, those would be:

    # Pre-order
    if not root:
        return root
    root.left, root.right = root.right, root.left
    self.invertTree(root.left)
    self.invertTree(root.right)
    return root
    
    # In-order
    if not root:
        return root
    self.invertTree(root.left)
    root.left, root.right = root.right, root.left
    self.invertTree(root.left)
    return root
    
    # Post-order (this is the longer version of @StefanPochmann 's first solution)
    if not root:
        return root
    self.invertTree(root.left)
    self.invertTree(root.right)
    root.left, root.right = root.right, root.left
    return root
    

    The first two recursive solutions don't allow for recursive calls to be compressed into one line, but post-order version does, so it is preferable.

    Since in-, pre- and post-order recursive traversals can all be converted into their respective iterative forms, any one of those will work, but from the iterative implementation logic pre-order is easier than in-order and in-order is in turn easier than post-order, so if we need an iterative solution, it would make sense for us to choose the iterative pre-order in an interview, which Stefan did here in his explicit stack solution. I personally prefer though to maintain an invariant of no None's in the stack, since it saves on number of append calls and while loop iterations at the expense of if checks which are cheaper, so I usually do this:

    if not root:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left  #specific to this problem
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return root
    

Log in to reply
 

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