An one-pass solution


  • 0
    C

    Calculate the Weighted sum ("ret" in the helper function) as in the previous problem, and at the same time record the total unweighted sum and the depth of the nested list. The inverse depth sum is:
    Unweighted Sum*(depth+1)-Weighted Sum.

    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int ret=0;
        auto tmp=helper(nestedList,ret,1);
        ret=tmp.first*(tmp.second+1)-ret;
        return ret;
    }
    
    pair<int,int> helper(vector<NestedInteger>& nestedList, int& ret, int d) {
        int h=1;
        int sum=0;
        for(int i=0;i<nestedList.size();++i) {
            if(nestedList[i].isInteger()) {
                sum+=nestedList[i].getInteger();
                ret+=d*nestedList[i].getInteger();
            }    
            else {
                auto tmp=helper(nestedList[i].getList(),ret,d+1);
                h=max(h,tmp.second+1);
                sum+=tmp.first;
            }
        }
        return {sum,h};
    }

Log in to reply
 

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