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

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

Solution 1：

想法：利用 BFS, 同 102. Binary Tree Level Order Traversal, 只是多了 reverse

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

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

        while (!q.empty()) {
            const int len = q.size();
            vector<int> level;

            for (int i = 0; i < len; ++i ) {
                const 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);
        }

        reverse(res.begin(), res.end());

        return res;
    }
};
  • time：$O(n)$ ➔ 每個 node 皆被遍歷一次
  • space：$O(n)$ ➔ 撇除要返回的 res, 在 while loop 迭代的過程中, q 的元素個數不超過 n

Solution 2：

想法：利用 DFS, 同 102. Binary Tree Level Order Traversal, 只是多了 reverse

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        dfs(root, 0, res);
        reverse(res.begin(), res.end());
        return res;
    }

private:
    void dfs(TreeNode* root, const 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