Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Space - O(h) ~ O(n) because its not a Balanced BT
Time - O(n)
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return root
temp = Solution.invertTree(self,root.left)
root.left = Solution.invertTree(self,root.right)
root.right = temp
return root