# LC 226. Invert Binary Tree

### [Problem link](https://leetcode.com/problems/invert-binary-tree/)

###### tags: `leedcode` `easy` `c++`

Given the <code>root</code> of a binary tree, invert the tree, and return its root.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg" style="width: 500px; height: 165px;" />

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

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg" style="width: 500px; height: 120px;" />

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

**Example 3:**

Input: root = []
Output: []

**Constraints:**

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

## Solution 1 - DFS
#### C++

class Solution {
public:
    TreeNode *invert(TreeNode *node) {
        if (node == nullptr) {
            return node;
        }
        TreeNode *left = node->left;
        TreeNode *right = node->right;
        node->right = invert(left);
        node->left = invert(right);
        return node;
    }

    TreeNode* invertTree(TreeNode* root) {
        return invert(root);
    }
};

## Solution 2 - BFS
#### C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode *> q;

        if (root != nullptr) {
            q.push(root);
        }
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();

            TreeNode *tmp = node->left;
            node->left = node->right;
            node->right = tmp;
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        return root;
    }
};

>### Complexity
>n = The number of nodes in the tree
>w = max width of the tree
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |
>| Solution 2 | O(n) | O(w) |

## Note
x