如何计算二叉搜索树（BST）节点层级和？现有方法返回0求排查

兄弟，我太懂这种卡了好几个小时、调试到怀疑人生的感觉！你遇到的问题大概率出在递归重载方法的逻辑实现上——从你给出的外层方法来看，核心问题应该是递归过程中没有正确累加所有节点的层级值，导致最后只返回了根节点的初始层级0。

常见错误原因分析 #

你提到调试时初始阶段正常，但最后返回时重置为0，最可能的情况是你的递归方法没有把左右子树的层级和与当前节点的层级做累加，比如错误的写法可能是这样：

// 错误示例：只返回当前节点层级，忽略了左右子树的结果
private int sumOfLevels(Node node, int lvl) {
    if (node == null) {
        return 0;
    }
    // 这里调用了递归，但没有接收返回值也没累加
    sumOfLevels(node.left, lvl + 1);
    sumOfLevels(node.right, lvl + 1);
    // 最后只返回当前节点的层级，上层调用根本没拿到子树的总和
    return lvl;
}

这种写法里，递归调用左右子树的结果完全被丢弃了，最后只会返回根节点的初始层级0，自然总和就是0。

正确的递归实现 #

要解决这个问题，关键是在递归中把当前节点的层级值，加上左右子树递归返回的层级和，最终返回累加后的结果：

// 外层入口方法（你已写的部分）
public int sumOfLevels() {
    return sumOfLevels(_root, 0);
}

// 核心递归方法
private int sumOfLevels(Node node, int currentLevel) {
    // 终止条件：空节点对总和没有贡献，返回0
    if (node == null) {
        return 0;
    }
    // 累加当前层级 + 左子树的层级和 + 右子树的层级和
    return currentLevel 
           + sumOfLevels(node.left, currentLevel + 1) 
           + sumOfLevels(node.right, currentLevel + 1);
}

调试小技巧 #

如果还是不确定问题出在哪，可以在递归方法里加打印语句，跟踪每一步的层级和累加结果：

private int sumOfLevels(Node node, int currentLevel) {
    if (node == null) {
        System.out.println("空节点，返回0");
        return 0;
    }
    int leftSum = sumOfLevels(node.left, currentLevel + 1);
    int rightSum = sumOfLevels(node.right, currentLevel + 1);
    int total = currentLevel + leftSum + rightSum;
    System.out.printf("节点值：%d，当前层级：%d，累计总和：%d%n", node.val, currentLevel, total);
    return total;
}

这样你能清楚看到每一步的计算是否正确，很快就能定位到哪里的逻辑出了问题。

内容的提问来源于stack exchange，提问作者Collin Thompson