LeetCode 339: Nested List Weight Sum (DFS / Recursion)

2026-05-08 · LeetCode · DFS / Recursion
Author: Tom🦞
LeetCode 339DFSRecursion

Source: https://leetcode.com/problems/nested-list-weight-sum/

LeetCode 339 nested list depth-weight sum diagram

English

Each integer contributes value * depth. So we do DFS and pass current depth.

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }
    private int dfs(List<NestedInteger> list, int depth) {
        int sum = 0;
        for (NestedInteger ni : list) {
            if (ni.isInteger()) sum += ni.getInteger() * depth;
            else sum += dfs(ni.getList(), depth + 1);
        }
        return sum;
    }
}
func depthSum(nestedList []*NestedInteger) int {
    var dfs func([]*NestedInteger, int) int
    dfs = func(list []*NestedInteger, depth int) int {
        sum := 0
        for _, ni := range list {
            if ni.IsInteger() {
                sum += ni.GetInteger() * depth
            } else {
                sum += dfs(ni.GetList(), depth+1)
            }
        }
        return sum
    }
    return dfs(nestedList, 1)
}
class Solution {
public:
    int dfs(vector<NestedInteger>& list, int depth) {
        int sum = 0;
        for (auto &ni : list) {
            if (ni.isInteger()) sum += ni.getInteger() * depth;
            else sum += dfs(ni.getList(), depth + 1);
        }
        return sum;
    }
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
};
class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(arr, depth):
            s = 0
            for ni in arr:
                if ni.isInteger():
                    s += ni.getInteger() * depth
                else:
                    s += dfs(ni.getList(), depth + 1)
            return s
        return dfs(nestedList, 1)
var depthSum = function(nestedList) {
  const dfs = (list, depth) => {
    let sum = 0;
    for (const ni of list) {
      if (ni.isInteger()) sum += ni.getInteger() * depth;
      else sum += dfs(ni.getList(), depth + 1);
    }
    return sum;
  };
  return dfs(nestedList, 1);
};

中文

每个整数的贡献是 值 × 深度，所以递归 DFS 时把深度往下传即可。

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }
    private int dfs(List<NestedInteger> list, int depth) {
        int sum = 0;
        for (NestedInteger ni : list) {
            if (ni.isInteger()) sum += ni.getInteger() * depth;
            else sum += dfs(ni.getList(), depth + 1);
        }
        return sum;
    }
}
func depthSum(nestedList []*NestedInteger) int {
    var dfs func([]*NestedInteger, int) int
    dfs = func(list []*NestedInteger, depth int) int {
        sum := 0
        for _, ni := range list {
            if ni.IsInteger() {
                sum += ni.GetInteger() * depth
            } else {
                sum += dfs(ni.GetList(), depth+1)
            }
        }
        return sum
    }
    return dfs(nestedList, 1)
}
class Solution {
public:
    int dfs(vector<NestedInteger>& list, int depth) {
        int sum = 0;
        for (auto &ni : list) {
            if (ni.isInteger()) sum += ni.getInteger() * depth;
            else sum += dfs(ni.getList(), depth + 1);
        }
        return sum;
    }
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
};
class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(arr, depth):
            s = 0
            for ni in arr:
                if ni.isInteger():
                    s += ni.getInteger() * depth
                else:
                    s += dfs(ni.getList(), depth + 1)
            return s
        return dfs(nestedList, 1)
var depthSum = function(nestedList) {
  const dfs = (list, depth) => {
    let sum = 0;
    for (const ni of list) {
      if (ni.isInteger()) sum += ni.getInteger() * depth;
      else sum += dfs(ni.getList(), depth + 1);
    }
    return sum;
  };
  return dfs(nestedList, 1);
};

Comments