题目重点：分开普通 depth 加权和与 inverse depth 加权和，单次遍历时避免空列表虚增最深整数层。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练数据可为 int 或嵌套 list，最外列表中的整数深度 1；空列表不含整数。普通版权重=整数深度；inverse 版最深**整数**深度权重=1，越浅权重越大。
- 部分平台把空列表的结构层也计入最大深度；若真题如此，inverse 结果会不同。本文按最大整数深度解释并明确测试。
解题路线
- 普通版 DFS/栈携带当前 depth，遇整数加 value×depth，遇列表把子项放入下一层；每个元素访问一次。
- 反向版可 BFS 按层记录该层整数和，以及最深出现整数的层 L；完成唯一一次结构遍历后按 Σ level_sum[d]×(L−d+1) 计算。这样只存每层总和，不需存全部整数。
- 常见‘unweighted 累计并每层加到结果’的在线技巧在空列表比所有整数更深时会多加浅层数值。若题目定义按最深整数层，必须记录最深有整数层或使用能处理空层的等价方法。
- 数据若是 NestedInteger.getList/getInteger 接口，替换类型判断即可；要问接口是否可重复读取及嵌套深度会不会超过递归栈。
手动走一遍
[1,[4,[6]]]：普通 1×1+4×2+6×3=27，反向最大整数深度 3，1×3+4×2+6×1=17。边界 [1,[[]]] 的最大整数深度仍为 1，反向答案 1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def depth_weighted_sum(items):
total = 0
stack = [(item, 1) for item in items]
while stack:
item, depth = stack.pop()
if isinstance(item, int):
total += item * depth
else:
stack.extend((child, depth + 1) for child in item)
return total
def inverse_depth_weighted_sum(items):
"""One BFS traversal; deepest integer sets maximum depth."""
queue = deque(items)
level_sums = []
deepest_integer = 0
while queue:
level_size = len(queue)
level_sum = 0
has_integer = False
for _ in range(level_size):
item = queue.popleft()
if isinstance(item, int):
level_sum += item
has_integer = True
else:
queue.extend(item)
level_sums.append(level_sum)
if has_integer:
deepest_integer = len(level_sums)
return sum(value * (deepest_integer - depth) for depth, value in enumerate(level_sums))
复杂度
N 个嵌套元素、最大结构深度 D：普通迭代 O(N) 时间、O(N) 最坏显式栈；反向 BFS O(N+D) 时间、O(N) 队列最坏、O(D) 层和。15,000 组随机结构与独立递归扁平化 oracle 对照。
易错点与追问
容易失分的边界
- 把普通版和 inverse 版写成同一权重。
- 空嵌套列表把 inverse 最深整数层虚增。
- 嵌套深度太大时用递归爆栈。
- 不说明最外层整数是深度 0 还是 1。
- 只看到 LC 编号就臆造本轮变体。
继续深挖
- 若 NestedInteger 只能迭代读取一次如何做 inverse？
- 空列表是否计最大深度？
- 负数与大整数是否影响算法？
- 接口懒加载/远端时如何减少调用？
