Python solutions (recursively, dfs, bfs).


  • 25
    C
    # recursively
    def invertTree1(self, root):
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
            
    # BFS
    def invertTree2(self, root):
        queue = collections.deque([(root)])
        while queue:
            node = queue.popleft()
            if node:
                node.left, node.right = node.right, node.left
                queue.append(node.left)
                queue.append(node.right)
        return root
        
    # DFS
    def invertTree(self, root):
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack.extend([node.right, node.left])
        return root

  • 0
    L

    i tried to do similar code as your recursively, but it was failed. Any reason for that?
    root.left = self.invertTree(root.right),
    root.right = self.invertTree(root.left)


  • 0
    I

    your root.left gets erased in the first set.invertTree(root.right)


  • 0
    A

    for DFS one, given the example(4 2 7 1 3 6 9) in the question, I think the result is 4 7 2 3 1 9 6 instead of 4 7 2 9 6 3 1. what I think is wrong?


  • 0
    V

    @yabchexu Though it is 7 month later, I still reply you in case you still use leetcode. "Invert" for a node means switch its left child and right child instead of just switch its left child and right child's value.

    So in this case, we first switch 4's left and right child, which results in [4,7,2,6,9,1,3]
    And then switch 7 and 2's left/right child.


  • 0
    S
    This post is deleted!

  • 0
    F

    In your BFS solution, why is there a parenthesis outside root?
    queue = collections.deque([(root)])


Log in to reply
 

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