Invert Binary Tree
Examples
Example 1:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 3, 2, 7, 6, 5, 4]
Example 2:
Input: root = [3, 2, 1]
Output: [3, 1, 2]
Example 3:
Input: root = []
Output: []
Example 1:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 3, 2, 7, 6, 5, 4]
Example 2:
Input: root = [3, 2, 1]
Output: [3, 1, 2]
Example 3:
Input: root = []
Output: []
You are given the root of a binary tree root. Invert the binary tree and return its root.
0 <= The number of nodes in the tree <= 100-100 <= Node.val <= 100Use DFS recursion to swap the left and right children at every node. Return the node after inverting its subtrees. This works for empty trees and single-node trees.
Inverting a tree means every node's left and right subtrees are swapped. Recursively inverting both children and swapping them at the current node produces the correct inverted structure for the entire tree.
O(n)O(h) where h is tree heightclass Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root