递归计算链式BST节点总数返回错误值的问题求助

你的递归计算链式二叉搜索树（BST）节点总数的代码存在冗余的分支判断，而且虽然逻辑上看似覆盖了所有情况，但其实可以大幅简化；至于测试返回错误结果的问题，大概率是代码分支判断的冗余导致逻辑意外走了错误分支，或者你的传入参数、树结构的构建存在问题。

代码冗余问题拆解 #

你当前的代码分了5种场景（包括空树的情况），但递归计算节点数的核心逻辑其实非常简洁：

• 如果当前节点为null，直接返回0（空树/空子树）
• 否则，返回「1（当前节点） + 左子树节点总数 + 右子树节点总数」

你写的那些分支判断完全是多余的——因为当左子树为空时，size(root.getLeft())会返回0；右子树为空时同理。比如：

• 当节点只有左子树时，1 + size(left) + 0 完全等价于你写的size(left)+1
• 当节点是叶子节点时，1 + 0 + 0 和你写的return 1效果一致

冗余的分支不仅增加了代码复杂度，还可能在某些边缘场景下引发逻辑错误。

修正后的极简代码 #

把代码简化成如下形式即可，逻辑清晰且不易出错：

private int size(BinaryTreeNode<T> root) {
    if (root == null) {
        return 0;
    }
    return 1 + size(root.getLeft()) + size(root.getRight());
}

为什么原代码返回错误的1？ #

你提到测试的树应该有6个节点，但原代码返回1，这说明你的代码走到了第二个分支：root.getRight() == null && root.getLeft() == null，也就是程序认为你传入的root是一个叶子节点。可能的原因有这几个：

• 你传入的root并非整棵树的根节点，而是某个叶子节点
• 你的BinaryTreeNode类的getLeft()或getRight()方法存在bug，明明有子节点却返回了null
• 你描述的树结构和实际代码中构建的树不一致，比如实际构建的树只有一个根节点

你可以先检查传入的root是否正确指向整棵树的根，再验证getLeft()和getRight()方法的正确性，最后用简化后的代码测试，应该就能得到正确的节点数了。

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