102. Binary Tree Level Order Traversal

題目網址：https://leetcode.cn/problems/binary-tree-level-order-traversal/

題意：給一 BT root, 返回 node.val 之 level-order（由上層往下層, 每層由左至右）。

Solution 1：

想法：利用 BFS

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) {
            return {};
        }

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

        while (!q.empty()) {
            vector<int> level;
            for (int i = q.size(); i > 0; --i) {
                auto cur = q.front();
                q.pop();
                level.emplace_back(cur->val);

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

                if (cur->right) {
                    q.emplace(cur->right);
                }
            }
            res.emplace_back(level);
        }
        return res;
    }
};

• time：$O(n)$ ➔ 每個 node 皆被遍歷一次
• space：$O(n)$ ➔ 若不考慮要返回的 array, q 的元素個數不超過 n

Solution 2：

想法：利用 DFS

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(root, 0, res);
        return res;
    }

private:
    void dfs(TreeNode* root, int depth, vector<vector<int>>& res){
        if (!root) {
            return;
        }

        while (res.size() <= depth) {
            res.emplace_back(vector<int>{});
        }

        res[depth].emplace_back(root->val);
        dfs(root->left, depth + 1, res);
        dfs(root->right, depth + 1, res);
    }
};

• time：$O(n)$ ➔ 每個 node 皆被遍歷一次
• space：$O(n)$ ➔ 遞迴深度不超過 n