Given the root of a binary tree, invert the tree, and return its root.
- First we will have to look at the root node, take its children, swap the positions of the children, then recursively run invert on both right and left subtrees. DFS will allow us to solve this problem
Depth For Search (DFS) - is an algorithm for traversing or searching tree. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
# swap the positions of the children
#saving the left value in a temporary variable
tmp = root.left
#replacing the left value(root.left) to with right value(root.right)
root.left =root.right
#replacing the right value(root.right) with the left which we saved as "tmp"
root.right = tmp
#invert left subtree
self.invertTree(root.left)
#invert right subtree
self.invertTree(root.right)
return root
Top comments (0)