226. Invert Binary Tree

1. Description

Given the root of a binary tree, invert the tree, and return its root.

2. Example

Example 1

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

Example 2

Input: root = [2,1,3]
Output: [2,3,1]

Example 3

Input: root = []
Output: []

3. Constraints

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

4. Solutions

Depth-First Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(logn->n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    TreeNode *invertTree(TreeNode *root) {
        if (root != nullptr) {
            swap(root->left, root->right);
            invertTree(root->left);
            invertTree(root->right);
        }

        return root;
    }
};