# 【LeetCode】226. Invert Binary Tree

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

## Intuition
> Given the `root` of a binary tree, invert the tree, and return _its root_.
(給定一個二元樹，請翻轉整個樹)

1. Recursive
* ✔️ Pre-order, NLR(Node-Left-Right)
* ✔️ In-order, LNR(Left-Node-Right)
* ✔️ Post-order, LRN(Left-Right-Node)
3. Queue(FIFO) 先訪問先處理

## Approach

### Recursive
1. 確認遞迴函數的回傳值與參數
首先題目要要求返回經過翻轉後的二元樹的根節點，因此返回值為 `TreeNode*` ，傳入參數為 `root`
2. 確認中止遞迴的條件
只要訪問到空的節點，就直接回傳 `nullptr`
3. 確認單層的遞迴邏輯
因為是要交換一個節點下左右兩個子節點，因此在Preorder尋訪中，我們要先透過 `swap` 函數交換兩個左

:::danger
在Inorder中的順序是先將左子樹進行翻轉，再翻轉根結點，因此未翻轉的右子樹此時變成左子樹，我們要將左子樹再翻轉一次
:::

### Queue
1. 使用 `Queue` 來進行 level-order traversal
2. 邏輯與 Recursive 解法差不多，只要交換訪問到的節點，就交換左右兩個子樹

## Complexity

- Time complexity: $O(n)$
$T(n) = 2 \times T(\frac{n}{2}) + O(1)$
- Space complexity: $O(n)$
- worse case: $O(n)$
- best cast: $\log (n)$

## Code

### Solution 1 Recursive

#### Preorder

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

#### Inorder

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

#### Postorder

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

### Solution 2 Queue

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* front = q.front();
                q.pop();
                swap(front->right, front->left);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }
        return root;
    }
};