3-4 lines Python


  • 48
    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


  • 3

    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.


  • 0
    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> <


Log in to reply
 

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