LeetCode 226: Invert Binary Tree

Explanation

To invert a binary tree, we swap the left and right children of every node in the tree recursively starting from the root. This can be done using a simple depth-first search (DFS) algorithm. The base case is when we reach a leaf node where we don't have any children to swap.

Algorithm:

1. If the root is null, return null.
2. Recursively call invertTree function on the left and right subtrees.
3. Swap the left and right children of the current root.
4. Return the modified root.

Time Complexity: O(n) where n is the number of nodes in the binary tree. Space Complexity: O(n) for the recursive call stack.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        
        root.left = right;
        root.right = left;
        
        return root;
    }
}