subject

Topic linking
Given a nested list of integers nestedList , Each element is either an integer , Or a list . meanwhile , The elements in the list can also be integers or another list .

The integer depth Is the number of nesting levels within the list . for example , Nested list [1,[2,2],[[3],2],1] The value of each integer in is its depth .

Please return the sum of all integers after the list is weighted by depth .

Example 1：

Input ：nestedList = [[1,1],2,[1,1]]
Output ：10
explain ： Because there are four depths in the list 2 Of 1 , And a depth of 1 Of 2.
Example 2：

Input ：nestedList = [1,[4,[6]]]
Output ：27
explain ： One depth is 1 Of 1, One depth is 2 Of 4, One depth is 3 Of 6. therefore ,1 + 42 + 63 = 27.
Example 3：

Input ：nestedList = [0]
Output ：0

Tips ：

1 <= nestedList.length <= 50
The value of an integer in the nested list is in the range [-100, 100] Inside
The maximum of any integer depth Are less than or equal to 50

Ideas

Linear traversal can be achieved through recursion , So as to solve the problem quickly .

Code

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the 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;
 * };
 */
class Solution {
public:
    int step = 0;
    int depthSum(vector<NestedInteger>& nestedList) {
        int ans = 0;
        ++ step;
        int n = nestedList.size();
        for(int i = 0; i < n; ++ i)
        {
            if(nestedList[i].isInteger())
            {
                ans += nestedList[i].getInteger() * step;
            }
            else{
                ans += depthSum(nestedList[i].getList());
            }
        }
        -- step;
        return ans;
    }
};

What's good here is mainly the realization depthSum Reuse of this function , By introducing external step, Used to guide the current depthSum Calculated layers , Then recover layer by layer , Its final implementation is completed in linear time .

Complexity analysis

Because it's linear , Its time complexity $\mathcal{O}(n)$
The spatial complexity may be $\mathcal{O}(1)$？