Two pass C++ solution


  • 1

    The first pass find the max level of nested list. Then the second pass computes the result. Time complexity O(n).

    void getLevel(vector<NestedInteger>& nestedList, int level, int& maxLevel) {
        maxLevel = std::max(level, maxLevel);
        for (NestedInteger ni : nestedList) {
            if (!ni.isInteger()) {
                getLevel(ni.getList(), level + 1, maxLevel);
            }
        }
    }
    int depthSumInverse(vector<NestedInteger>& nestedList, int level) {
        int sum = 0;
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {
                sum += ni.getInteger() * level;
            } else {
                sum += depthSumInverse(ni.getList(), level - 1);
            }
        }
        return sum;
    } 
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int maxLevel = 0;
        getLevel(nestedList, 1, maxLevel);
        return depthSumInverse(nestedList, maxLevel);
    }

Log in to reply
 

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