226. Invert Binary Tree

題目網址：https://leetcode.cn/problems/invert-binary-tree/

題意：給一 BT, 反轉其左右子樹。

Solution 1：

想法：利用 DFS

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) {
            return root;
        }

        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

time：$O(n)$ ➔ 遍歷整個 BT
space：$O(n)$ ➔ worse case：skew tree, 遞迴深度為 n

Solution 2：

想法：利用 BFS

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) {
            return root;
        }

        queue<TreeNode*> q;
        q.emplace(root);

        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            swap(cur->left, cur->right);

            if (cur->left) {
                q.emplace(cur->left);
            }

            if (cur->right) {
                q.emplace(cur->right);
            }
        }

        return root;
    }
};

time：$O(n)$ ➔ 遍歷整個 BT
space：$O(n)$ ➔ q 中的元素個數不超過 n