层数最深叶子节点的和

记住「队列按层展开,每层把 s 重新算一遍,循环结束时 s 就是最深层的和」,下面逐帧套它。

什么是最深层：先找感觉:同一深度的节点是同一层。一层层往下,最深的是第 4 层的 70 和 85(蓝色),它们下面再没有节点。我们要的就是这最深一层的和。

第 1 层就位：进入第 1 层,队列里是 [50]。把 s 清零,再从左到右扫这一整层、边扫边累加。

第 1 层 · 累加：从队首取出 50(红色高亮),把它加进本层和 s:0 加 50 得到 50。

第 1 层 · 收孩子：50 加完了。把它的非空孩子 30、80(蓝色)加入下一层,目前下一层攒到了 [30、80]。

第 1 层和 = 50：第 1 层扫完,本层和 s 是 50。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 50 当作「最后一层的和」记着。

第 2 层就位：进入第 2 层,队列里是 [30、80]。把 s 清零,再从左到右扫这一整层、边扫边累加。

第 2 层 · 累加：从队首取出 30(红色高亮),把它加进本层和 s:0 加 30 得到 30。

第 2 层 · 收孩子：30 加完了。把它的非空孩子 20、40(蓝色)加入下一层,目前下一层攒到了 [20、40]。

第 2 层 · 累加：从队首取出 80(红色高亮),把它加进本层和 s:30 加 80 得到 110。

第 2 层 · 收孩子：80 加完了。把它的非空孩子 60、90(蓝色)加入下一层,目前下一层攒到了 [20、40、60、90]。

第 2 层和 = 110：第 2 层扫完,本层和 s 是 110。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 110 当作「最后一层的和」记着。

第 3 层就位：进入第 3 层,队列里是 [20、40、60、90]。把 s 清零,再从左到右扫这一整层、边扫边累加。

第 3 层 · 累加：从队首取出 20(红色高亮),把它加进本层和 s:0 加 20 得到 20。

第 3 层 · 收孩子：20 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 3 层 · 累加：从队首取出 40(红色高亮),把它加进本层和 s:20 加 40 得到 60。

第 3 层 · 收孩子：40 加完了。把它的非空孩子 70、85(蓝色)加入下一层,目前下一层攒到了 [70、85]。

第 3 层 · 累加：从队首取出 60(红色高亮),把它加进本层和 s:60 加 60 得到 120。

第 3 层 · 收孩子：60 是叶子,没有孩子可加,下一层暂时还是 [70、85]。

第 3 层 · 累加：从队首取出 90(红色高亮),把它加进本层和 s:120 加 90 得到 210。

第 3 层 · 收孩子：90 是叶子,没有孩子可加,下一层暂时还是 [70、85]。

第 3 层和 = 210：第 3 层扫完,本层和 s 是 210。它的孩子组成了下一层,所以 s 之后还会被下一层重新算一遍,目前先把 210 当作「最后一层的和」记着。

第 4 层就位：进入第 4 层,队列里是 [70、85]。把 s 清零,再从左到右扫这一整层、边扫边累加。

第 4 层 · 累加：从队首取出 70(红色高亮),把它加进本层和 s:0 加 70 得到 70。

第 4 层 · 收孩子：70 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 4 层 · 累加：从队首取出 85(红色高亮),把它加进本层和 s:70 加 85 得到 155。

第 4 层 · 收孩子：85 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 4 层和 = 155：第 4 层扫完,本层和 s 是 155。这一层每个节点都没有孩子,队列即将空,它就是最深一层,s = 155 就是最终答案。

完成：四层的和依次是 50、110、210、155。最深的是第 4 层(金色 70、85),它的和 155 就是答案。特别注意:第 3 层的和 210 反而更大,但我们要的是最深那层,不是和最大的那层。回头看,就是一遍按层 BFS,每层重算一次 s,循环结束时 s 自然停在最深层,时间 O(n)。

边界:单节点返回自身、链返回链尾、最深层多节点则求和。

两个追问:DFS 带 depth 维护最大深度与其和;无需先找叶子再筛。