Leetcode 339. Nested List Weight Sum

题目

Given a nested list of integers, return the sum of all integerss 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.

思路

题目要求我们对nestedList进行求和。仔细读题我们发现，nestedList中要么为普通的Integer（我们可以直接求和）， 要么为下一层nestedList（需要我们继续用相同的方法求和）。这提示我们应用递归的思想，因为我们在不断的处理性质相同的问题。 不过，值得注意的是，求和时需要将每个元素按照其深度加权。递归恰好能帮我们完成这一点：我们只需要在递归/DFS时，记录当前层数即可。

解答

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {

    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }

    // Recursively unnest list and find sum
    private int dfs(List<NestedInteger> nestedList, int level) {
        if (nestedList.size() == 0) return 0;
        int sum = 0;
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {                
                sum += (ni.getInteger() * level);
            }
            else {
                sum += dfs(ni.getList(), level + 1);
            }
        }
        return sum;
    }
}

Complexity Analysis:

• Time Complexity: O(n). 我们需要通过DFS遍历所有的NestedElement（包括Integer和NestedList）。

• Space Complexity: O(n). 递归每往下一层就需要占用一次stack space，因此最坏情况下需要O(n)的栈空间。

拓展

• 如果不用递归，而仅采用循坏，我们可以解决这道题吗？两者有什么区别呢？

总结

这类题目相对基础，但是依然需要我们核心的两个步骤：一为判断出这道题目考察知识点为Graph, DFS和递归； 二为我们熟练地bug-free地完成代码的书写。

Reference

• Leetcode Official Solution