# Share my C++ solutions: two-pass and BFS

• Two-pass:

class Solution {
private:
void find_height(vector<NestedInteger>& nestedList, int cur_level, int& max_level) {
max_level = max(max_level, cur_level);
for (auto& x : nestedList)
if (!x.isInteger())
find_height(x.getList(), cur_level + 1, max_level);
}

int level_sum(vector<NestedInteger>& nestedList, int cur_level) {
int sum = 0;
for (auto& x : nestedList) {
if (x.isInteger()) sum += cur_level * x.getInteger();
else sum += level_sum(x.getList(), cur_level - 1);
}
return sum;
}
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
int max_level = 0, sum = 0;
find_height(nestedList, 1, max_level);
return level_sum(nestedList, max_level);
}
};

BFS:

class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
typedef vector<NestedInteger>::iterator ListIterator;
queue<pair<ListIterator, ListIterator>> nextQueue;
queue<pair<ListIterator, ListIterator>> curQueue;
int weighted = 0, unweighted = 0;
nextQueue.push({nestedList.begin(), nestedList.end()});
while (!nextQueue.empty()) {
swap(curQueue, nextQueue);
while (!curQueue.empty()) {
auto first = curQueue.front().first, last = curQueue.front().second;
curQueue.pop();
for (; first != last; ++first) {
if (first -> isInteger())
unweighted += first -> getInteger();
else
nextQueue.push({first -> getList().begin(), first -> getList().end()});
}
}
weighted += unweighted;
}
return weighted;
}
};

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