Invert Binary Tree: the idea to remember.

The core insight

Recursively invert each subtree and swap their resulting roots.

Why it works

Each subtree is correctly mirrored by induction; swapping them mirrors the whole tree.

The mistake to avoid

Save the original child reference or compute both inverted children before overwriting either pointer.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

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;
}

Make the next connection