find-the-level-of-tree-with-minimum-sum.cpp

// Time:  O(n)
// Space: O(w)

// bfs
class Solution {
public:
    int minimumLevel(TreeNode* root) {
        static const int64_t INF = numeric_limits<int64_t>::max();

        vector<TreeNode *> q = {root};
        pair<int64_t, int64_t> result = {INF, INF};
        for (int64_t d = 1; !empty(q); ++d) {
            vector<TreeNode *> new_q;
            int64_t total = 0ll;
            for (const auto& u : q) {
                if (u->left) {
                    new_q.emplace_back(u->left);
                }
                if (u->right) {
                    new_q.emplace_back(u->right);
                }
                total += u->val;
            }
            result = min(result, pair(total, d));
            q = move(new_q);
        }
        return result.second;
    }
};