Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

 

Example 1:

Input: [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1.

 

Example 2:

Input: [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.

 

/*

// This is the interface that allows for creating nested lists.

// You should not implement it, or speculate about its implementation

class NestedInteger {

  // constructor initializes an empty nested list

  NestedInteger();

  // constructor initializes a single integer

  NestedInteger(int value);

  // return true if this NestedInteger holds a single integer that this NestedInteger holds, if it holds a single integer

  // the result is undefined if this NestedInteger holds a nested list

  int getInteger() const;

  // set this NestedInteger to hold a single integer

  void setInteger(int value);

  // set this NestedInteger to hold a nested list and adds a nested integer to it.

  void add(const NestedInteger &ni);

  // return the nested list that this NestedInteger holds, if it holds a nested list

  // the result is undefined if this NestedInteger holds a single integer

  const vector<NestedInteger> &getList() const;

};

*/

//! 0ms(faster than 100%)

class Solution {
public:
    int getSum(vector& nestedList, int level, int sum)
    {
        if(nestedList.size() == 0) return sum;
        for(int i = 0; i < nestedList.size(); i++)
        {
            NestedInteger each = nestedList.at(i);
            if(each.isInteger())
            {
                 sum += (each.getInteger() * level);
            }
            else
            {
                 sum = getSum(each.getList(), level+1, sum);
            }
        }
        return sum;
    }
    int depthSum(vector& nestedList) {
        return getSum(nestedList, 1, 0);
    }
};

 

//! 4ms(faster than 65.78%)

class Solution {
public:
    int getSum(vector& nestedList, int level)
    {
        if(nestedList.size() == 0) return 0;
        int sum = 0;
        for(int i = 0; i < nestedList.size(); i++)
        {
            NestedInteger each = nestedList.at(i);
            if(each.isInteger())
            {
                 sum += (each.getInteger() * level);
            }
            else
            {
                 sum += getSum(each.getList(), level+1);
            }
        }
        return sum;
    }
    int depthSum(vector& nestedList) {
        return getSum(nestedList, 1);
    }
};