AlgoNote 算法通关手册：LeetCode 0364 嵌套列表加权和 II —— 两次遍历求解逆深度加权和

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文讲解 LeetCode 0364「嵌套列表加权和 II」的完整解题方案。与 0339「嵌套列表加权和」不同本题的权重与整数的深度成反比越深层的整数权重越小因此必须先求出整个嵌套列表的最大深度再反向加权求和。读完本文你将掌握基于NestedInteger接口的递归遍历套路、最大深度求解方法与逆深度加权和的实现并能将同一套模板迁移到同类嵌套列表问题中。一、题目概述题目来源LeetCode 0364「嵌套列表加权和 II」标签为栈、深度优先搜索、广度优先搜索难度中等。1.1 问题描述给定一个整数嵌套列表nestedList每一个元素要么是一个整数要么是一个列表这个列表中的每个元素也同样是整数或列表。本题涉及两个核心概念深度整数的「深度」取决于它位于多少个列表内部。例如嵌套列表[1,[2,2],[[3],2],1]的每个整数的值都等于它的深度。令maxDepth是任意整数的「最大深度」。权重整数的「权重」为maxDepth - (整数的深度) 1。要求将nestedList列表中每个整数先乘权重再求和返回该加权和。1.2 题目说明与数据范围约束项范围嵌套列表长度1 ≤ nestedList.length ≤ 50整数取值[-10³, 10³]任意整数的最大深度小于等于50空列表不存在无需处理空列表边界从数据范围可以看出最大深度不超过 50因此递归深度完全在 Python 默认递归限制约 1000之内可以放心使用递归解法。二、示例拆解先理解权重的「反转」本题与 0339 的差别在于权重方向完全相反0339 中越深的整数权重越大权重 深度而 0364 中越深的整数权重越小权重 maxDepth - depth 1。示例 1输入nestedList [[1,1],2,[1,1]] 输出8解析4 个1位于深度 2 的位置1 个2位于深度 1 的位置。最大深度maxDepth 2因此深度 2 的1权重 2 - 2 1 1深度 1 的2权重 2 - 1 1 2。加权和为1*1 1*1 2*2 1*1 1*1 8。示例 2输入nestedList [1,[4,[6]]] 输出17解析1 个1位于深度 3 的位置1 个4位于深度 2 的位置1 个6位于深度 1 的位置。最大深度maxDepth 3因此深度 3 的1权重 3 - 3 1 1深度 2 的4权重 3 - 2 1 2深度 1 的6权重 3 - 1 1 3。加权和为1*1 4*2 6*1 17。注意一个关键点6本身位于最深层深度 3但因为权重公式是maxDepth - depth 1它反而获得了最小权重 1。这正是本题名称中「II」与 0339 的核心区别。三、解题思路两次遍历DFS 递归由于权重依赖全局的maxDepth而maxDepth在遍历完成前是未知的因此无法像 0339 那样单次遍历直接求和。本题的标准解法分两步第一次遍历——计算最大深度使用深度优先搜索遍历整个嵌套列表记录每个整数的深度并更新最大深度maxDepth。第二次遍历——计算加权和再次遍历嵌套列表对于每个整数其权重为maxDepth - depth 1其中depth是该整数的深度将所有整数的值乘以其权重后求和。3.1 具体步骤定义递归函数getMaxDepth(nestedList, depth)用于计算最大深度定义递归函数calculateSum(nestedList, depth, maxDepth)用于计算加权和对每个NestedInteger元素如果是整数则在计算最大深度时进行比较和更新在计算加权和时累加当前值乘以权重如果是列表则递归地处理其内部元素深度加 1。3.2 完整代码实现# # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # #class NestedInteger: # def __init__(self, valueNone): # # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # # def isInteger(self): # # return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # # def add(self, elem): # # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # # def setInteger(self, value): # # Set this NestedInteger to hold a single integer equal to value. # :rtype void # # def getInteger(self): # # return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # # def getList(self): # # return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # class Solution: def depthSumInverse(self, nestedList: List[NestedInteger]) - int: # 第一次遍历计算最大深度 max_depth self.getMaxDepth(nestedList, 1) # 第二次遍历计算加权和 return self.calculateSum(nestedList, 1, max_depth) def getMaxDepth(self, nestedList: List[NestedInteger], depth: int) - int: 计算嵌套列表的最大深度 max_depth depth for item in nestedList: if item.isInteger(): # 如果是整数更新最大深度 max_depth max(max_depth, depth) else: # 如果是列表递归计算子列表的最大深度 max_depth max(max_depth, self.getMaxDepth(item.getList(), depth 1)) return max_depth def calculateSum(self, nestedList: List[NestedInteger], depth: int, max_depth: int) - int: 计算加权和 total_sum 0 for item in nestedList: if item.isInteger(): # 如果是整数计算其加权贡献 # 权重 max_depth - depth 1 weight max_depth - depth 1 total_sum item.getInteger() * weight else: # 如果是列表递归计算子列表的加权和 total_sum self.calculateSum(item.getList(), depth 1, max_depth) return total_sum3.3 代码要点解读入口depthSumInverse两次调用辅助函数第一次以深度 1 为起点求max_depth第二次同样从深度 1 出发携带max_depth计算加权和。两次遍历共享同一个根列表因此总时间复杂度为 $O(n)$ 的常数倍。getMaxDepth的边界处理初始将max_depth设为当前depth对每个整数元素与当前深度取max更新遇到子列表则递归时深度加 1。即使某一层全是列表没有整数max_depth也能正确维护因为整数层的深度会被递归路径中的整数节点捕获。calculateSum的权重计算weight max_depth - depth 1是本题唯一与 0339 不同的核心公式。注意权重最小为 1最深层整数最大为max_depth最外层整数与「越深权重越小」的直觉一致。负数处理由于整数取值范围含负数[-10³, 10³]item.getInteger() * weight的累加对负数同样适用无需额外处理符号。四、复杂度分析时间复杂度$O(n)$其中 $n$ 是嵌套列表中所有整数的总数。需要遍历两次嵌套列表每次遍历的时间复杂度都是 $O(n)$即访问每个NestedInteger节点一次。空间复杂度$O(d)$其中 $d$ 是嵌套列表的最大深度。递归调用栈的深度最多为 $d$且两次遍历各自独立递归不会叠加。由题目约束d ≤ 50递归栈空间非常有限这也是 DFS 递归方案在该数据规模下完全可行的原因。五、从仓库视角理解NestedInteger与同主题题目5.1NestedInteger接口的调用契约本题代码中反复使用的isInteger()、getInteger()、getList()来自 LeetCode 平台预置的NestedInteger接口见上文代码注释中的完整定义。它是处理嵌套列表类问题的统一抽象isInteger()判断当前NestedInteger保存的是单个整数还是嵌套列表getInteger()若保存的是整数则返回该整数否则返回None或调用结果未定义getList()若保存的是列表则返回List[NestedInteger]否则返回None或调用结果未定义。在解题时对每个元素先isInteger()分流再分别走整数分支与列表分支递归是这类题的统一模板。仓库中对同一抽象的使用可参考 扁平化嵌套列表迭代器题解该题用栈代替递归来实现延迟展开与本体的递归模板形成对照。5.2 同主题题目串联0339 → 0364 → 0341「嵌套列表」在 LeetCode 300 段是一个完整的小专题三题难度相当、思路互补建议按序刷完以建立体系化认知题号题目与本题的关系0339嵌套列表加权和正向加权权重 深度单次 DFS 即可是本题的前置基础与 0364 形成「正向 / 反向权重」的对照练习0364嵌套列表加权和 II反向加权权重 maxDepth - depth 1需要两次遍历即本文主题0341扁平化嵌套列表迭代器将嵌套列表扁平化的迭代器设计用栈延迟展开可用于检验对NestedInteger结构理解的熟练度从 0339 到 0364本质区别只有一个公式weight depth变成weight maxDepth - depth 1但引入的「先求全局最大深度再反向加权」的两阶段思维是面试中常被考察的变形点。若面试官要求在此基础上将两次遍历合并为一次如利用 BFS 逐层累加也是值得进一步思考的优化方向。六、总结LeetCode 0364「嵌套列表加权和 II」考察的是对递归树的遍历能力与「先收集全局信息、再依据全局信息计算」的两阶段思维深度与权重公式weight maxDepth - depth 1与 0339 的weight depth恰好相反解法模板getMaxDepth求最大深度 calculateSum反向加权求和两次独立的 DFS时间复杂度 $O(n)$、空间复杂度 $O(d)$复用价值isInteger() / getInteger() / getList()三分支递归模板可迁移至 0339 嵌套列表加权和 与 0341 扁平化嵌套列表迭代器 等同主题题目建议组合练习以彻底掌握嵌套列表类问题的解法体系。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐0339 嵌套列表加权和基于 DFS 深度遍历的 LeetCode 中等题实战解析AlgoNote 算法通关手册0339 嵌套列表加权和基于 DFS 深度遍历的 LeetCode 中等题实战解析AlgoNote 算法通关手册 导读 本篇以「算法通关手册」AlgoNo教程文档知识库gqlgen 错误处理完全指南向 GraphQL 响应发送自定义错误数据gqlgen 错误处理完全指南向 GraphQL 响应发送自定义错误数据 导读 本文以 gqlgen 官方参考文档 docs/content/referenc教程文档知识库AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析 全排列Permutations是回溯算法最经典的入门问题也是算法面试教程文档知识库上一篇告别小程序图片裁剪难题3分钟打造专业级图片处理体验下一篇终极指南如何用ESTabBarController快速打造惊艳的自定义TabBar组件库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考