如何统计二叉搜索树(BST)中拥有子节点的节点总数

• 你的核心统计需求是统计二叉树中至少存在1个子节点的非叶子节点总数，这类节点的判定逻辑非常简单：只要左子节点非空 或 右子节点非空，就算1个有效节点，不需要拆分左右分别统计再相加。
• 你当前的实现误差来源有两个：
  1. 重复计数：如果一个节点同时拥有左、右子节点，rightchild函数会统计它1次，leftchild函数也会统计它1次，同一个节点被重复计数了1次，这是你结果总有1的误差的核心原因。
  2. 逻辑冗余：拆分两个函数分别统计有左子、有右子的节点，完全没有必要，还会增加递归遍历的次数，性能更低。

你只需要一个递归函数就可以完成统计，实现代码如下：

static int countNonLeaf(const treeNode* tree) {
    // 空节点直接返回0
    if (tree == NULL) {
        return 0;
    }
    // 判断当前节点是否为非叶子节点
    int currentCount = (tree->left != NULL || tree->right != NULL) ? 1 : 0;
    // 递归统计左右子树的非叶子节点总和返回
    return currentCount + countNonLeaf(tree->left) + countNonLeaf(tree->right);
}

直接调用countNonLeaf(根节点)就能得到你要的统计结果，不需要再将两个函数结果相加。

如果要保留你原本拆分左右的写法，只需要对两个函数的结果做去重即可：总有效节点数 = 有右子的节点数 + 有左子但没有右子的节点数，即可避免重复计数，但该写法冗余度高，不推荐使用。

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