# Leetcode [No. 226] Invert Binary Tree(EASY)

+ First solved on 2023/12/16
+ Second solved on 2025/01/04

## 題目

https://leetcode.com/problems/invert-binary-tree/description/

## 思路
+ 這個題目用簡單的DFS搭配交換左子樹跟右子樹即可。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* node)
    {
        if(node==nullptr) return;
        if(node->left) dfs(node->left);
        if(node->right) dfs(node->right);
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
    }
};

### 解法分析
+ time complexity: O(lgn)

### 執行結果

## 改良:

+ 過了一年多又寫到這題，發現這題之前寫過，但因為會的coding技巧又多了幾種，看到這題直覺就會想用level-order-traversal(BFS)來做。
+ `swap(cur->left, cur->right)` 這一段是重點，因為我們要把左右翻轉。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // use bfs to level-order-traversal
        if (!root) return root;
        queue<TreeNode*> q;
        q.push(root);
        // bfs
        while (!q.empty())
        {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* cur = q.front();
                q.pop();
                swap(cur->left, cur->right);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return root;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

---

過了一個月都沒刷題，剛好寫個tree來練練手，發現我這次的寫法跟上次又不一樣了，這次的想法主要是用post-order的方式來做，其實跟DFS比較像

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        else {
            invertTree(root->left);
            invertTree(root->right);
            TreeNode* tmp = root->left;
            root->left = root->right;
            root->right = tmp;
            return root; 
        }
    }
};