Python DFS / BFS solution


  • 0
    T

    DFS version:

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

    BFS version:

    def bfs_invertTree(self, root):
            queue = collections.deque()
            if (root):
                queue.append(root)
    
            while(queue):
                node = queue.popleft()
                if (node.left):
                    queue.append(node.left)
                if (node.right):
                    queue.append(node.right)
                node.left, node.right = node.right, node.left
    
            return root

  • 0
    C

    It seems that you can complete BFS version like this as well:

    def invertTree(self, root):
        queue = []
        queue.append(root)
        while queue:
            curr = queue.pop(0)
            if curr:
                curr.left, curr.right = curr.right, curr.left
                queue.append(curr.left); queue.append(curr.right)
        return root

Log in to reply
 

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