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

題意：給一 BT 的 root, 返回 node.val 的 zigzag（鋸齒形）level order（先從左往右, 而下一層從右往左遍歷, 依此類推, 層與層之間交替進行）。

Solution 1：

想法：利用 BFS

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

        int depth = 0;
        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);
                }
            }

            if (depth % 2 == 1) {
                reverse(level.begin(), level.end());
            }

            depth++;
            res.emplace_back(level);
        }

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

Solution 2：

想法：利用 DFS

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(root, 0, res);
        for (int i = 1; i < res.size(); i += 2) {
            reverse(res[i].begin(), res[i].end());
        }
        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