C++, short code, O(n), no reversing


  • 0
    std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        std::vector<std::vector<int>> res;
        std::queue<std::pair<TreeNode*, int>> Q; //first: node, second: level
        Q.emplace(root, 0);
        for (bool everyother = true; !Q.empty(); everyother = !everyother) {
            res.push_back({});
            for (int i = 0, n = Q.size(); i < n; i++, Q.pop()) {
                auto node = Q.front().first;
                int level = Q.front().second;
                if (i == 0) res[level].resize(n);
                if (everyother) res[level][i] = node->val;
                else res[level][n-i-1] = node->val;
                if (node->left) Q.emplace(node->left, level + 1);
                if (node->right) Q.emplace(node->right, level + 1);
            }
        }
        return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.