朋友从某节跑路了，说强度太大了，早上10点，晚上10点。去了才不到三星期，不知道她有没有被拉黑简历

昨晚十一点多我刚躺下准备刷会儿视频，我们组那个小李突然在群里@我：“东哥，面试碰到个二叉树题，最大层内元素和，你咋写？”我人都快睡着了，只能爬起来拿起电脑，顺嘴跟他唠了半天。

这个题大概意思你们应该都见过：给你一棵二叉树，每一层节点都有若干整数值，把每一层的值加起来，看哪一层的总和最大，返回这一层的编号（一般是从 1 开始数根节点那层）。比如说，根节点这一层和是 5，下一层和是 7，再下一层和是 10，那就返回 3。

听起来挺生活化的，对吧，就好像数一下公司每一层楼有多少人，然后看哪一层最挤。

我当时跟小李说，这种题其实就两条路，要么深度优先（DFS）往下钻的时候顺便把“当前是第几层”带着，把每一层的和记录到一个数组里；要么干脆用广度优先（BFS），一层一层地扫，这个更符合人脑对“层”的直觉。面试的时候一般 BFS 更好讲一点。

我给他敲的代码是 BFS 版本，大概长这样（Java 写的哈）：

// LeetCode 上常见的二叉树节点定义
classTreeNode{
int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { 
this.val = val; 
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
    }
}

publicclassSolution{

publicintmaxLevelSum(TreeNode root){
if (root == null) {
return0; // 看具体题目要求，有的不会给空树
        }

        java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
        queue.offer(root);

int currentLevel = 0;    // 当前层从 1 开始数
int bestLevel = 1;       // 答案层
long bestSum = Long.MIN_VALUE; // 防止 int 溢出，保险一点

while (!queue.isEmpty()) {
int size = queue.size();  // 这一层有多少节点
            currentLevel++;
long levelSum = 0;

// 把这一层的节点都处理完
for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;

if (node.left != null) {
                    queue.offer(node.left);
                }
if (node.right != null) {
                    queue.offer(node.right);
                }
            }

// 更新最大和和对应层号
if (levelSum > bestSum) {
                bestSum = levelSum;
                bestLevel = currentLevel;
            }
        }

return bestLevel;
    }
}

当时我边讲边哈欠，你们简单感受一下这个流程哈：

先丢一个根节点到队列里，队列就好比电梯，哪一层的人全进电梯，我们就把这层所有人点名一遍（那就是 for 循环里那一坨），把他们工资加起来（levelSum += node.val），顺便把他们的左右孩子塞电梯里，准备下一层。每搞完一层，就看一下这一层的总和是不是目前最大的，是的话记一下“最好的一层是谁”。

这一整套遍历下来，每个节点只进队、出队一次，所以时间复杂度就是 O(N)，空间就是队列那点东西，最坏情况一层特别宽，就是 O(N)，一般面试官听你说到这儿就不会再追问了。

小李当时问了一句：“那 DFS 能不能写？”当然能啊，不过 DFS 写法就是换个姿势而已。脑子里记住一个“层号 -> 层和”的映射，比如用 List<Integer> 或 Map<Integer, Long>，递归的时候把当前层传下去：

publicclassSolutionDfs{

publicintmaxLevelSum(TreeNode root){
        java.util.List<Long> sums = new java.util.ArrayList<>();
        dfs(root, 0, sums); // 从第 0 层开始，等会儿返回的时候 +1 就行

long best = Long.MIN_VALUE;
int bestLevel = 0;
for (int i = 0; i < sums.size(); i++) {
if (sums.get(i) > best) {
                best = sums.get(i);
                bestLevel = i + 1; // 题目里层数从 1 开始
            }
        }
return bestLevel;
    }

privatevoiddfs(TreeNode node, int level, java.util.List<Long> sums){
if (node == null) {
return;
        }
if (level == sums.size()) {
            sums.add(0L);
        }
        sums.set(level, sums.get(level) + node.val);

        dfs(node.left, level + 1, sums);
        dfs(node.right, level + 1, sums);
    }
}

这个就像是在一条小路上一路往下走，每到一个深度你都顺手在“这一层的累计和”上加一下，走完整棵树再回头找哪一层最大。思路不难，就是递归多了栈空间开销，理论上最坏情况链表型的树会到 O(N)。

顺便插一句，我之前写数据库性能那篇对比文章的时候也用过类似“分层统计”的思路，只不过那会儿按的是 QPS 区间，不是树的层数，底层逻辑其实挺像：先分桶，再在桶里算最大值。

反正这个题你只要把“层序遍历”和“顺便求和”这两个词挂嘴边，代码像上面这样别写出什么离谱的 bug，面试官一般会点点头，然后开始问你别的坑了。

好了我不说了，我去给小李催简历进度了，你要是哪天被问到这题，记得想起我半夜起床讲算法这回事就行。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html