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
I try to change your second version to the following one, but it always has error:
invert = self.invertTree
root.left = invert(root.right)
root.right = invert(root.left)
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.
Thanks a lot! I will pay attention for the format! Now I know how to swap two variables in place by python!
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.
@amyshang77 Yes, it's both of those.
@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> <
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.