339. Nested List Weight Sum

The problem requires a depth so I intuitively think of DFS. And yes, DFS works fine with this problem. The idea is loop through the input list, check if it is an integer. If so, add the integer to the sum. If not, recursively call itself and add the returned value to the sum. After I'm done with the loop, return the sum.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class Solution {  
19:  public:  
20:    int depthSum(vector<NestedInteger>& nestedList) {  
21:      return helper(nestedList, 1);  
22:    }  
23:    int helper(vector<NestedInteger> &nestedList, int d) {  
24:      int sum = 0;  
25:      for (int i = 0; i < nestedList.size(); i++) {  
26:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
27:        else sum += helper(nestedList[i].getList(), d+1);  
28:      }  
29:      return sum;  
30:    }  
31:  };