Easy

Invert Binary Tree

Given the `root` of a binary tree, invert the tree, and return its root. Inverting a binary tree means swapping every left node with its corresponding right node.

Examples

Input:root = [4,2,7,1,3,6,9]

Output:[4,7,2,9,6,3,1]

Input:root = [2,1,3]

Output:[2,3,1]

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Approach

Use a recursive Depth-First Search (DFS) approach. The base case is when the current node is null, we return null. For a non-null node, we swap its left and right child pointers. Then, we recursively invert its left and right subtrees. Finally, return the current node.

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

Where n is the number of nodes and h is the height of the tree. The space complexity is due to the recursion stack.

Solution.java

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode invertTree(TreeNode root) {18        if (root == null) {19            return null;20        }21        22        // Swap the children23        TreeNode temp = root.left;24        root.left = root.right;25        root.right = temp;26        27        // Recursively invert the subtrees28        invertTree(root.left);29        invertTree(root.right);30        31        return root;32    }33}