有没有大神说一下为什么注释里面的不能求二叉树叶子的个数？

Question

int CountNode_Leaf(pBTNode t)
{
	int i = 0;
	if (!t) return 0;
	int l= CountNode_Leaf(t->LTree);
	int r =CountNode_Leaf(t->RTree);
	//if (!t->LTree && !t->RTree)
	//{
	//	//printf("00==%d",i);
	//	i = l + r + 1;
	//	return i;
	//}
	i = l + r + 1;
	if (t->LTree || t->RTree) i--;
	return i;
}

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

这段代码使用递归的方法来计算一个给定二叉树中叶子节点的数量。在这个问题中，我们没有使用到计数变量 i 或者其他任何变量来存储或更新结果。

在递归函数 CountNode_Leaf() 中，首先检查当前节点是否为空（即 t == NULL）。如果为真，则返回 0，表示这是一个空节点。

然后，我们分别对左子树和右子树进行递归调用，并将它们的结果累加起来：l = CountNode_Leaf(t->LTree) 和 r = CountNode_Leaf(t->RTree)。这实际上就是递归地计算了所有非叶子节点的数量。

最后，我们将两个累加结果相加并加上当前节点的值（即当前节点是叶子节点），并将这个总和减去已知的非叶子节点数量（即当前节点有且仅有一个子节点时的累加结果），以得到叶子节点的数量。这样做的目的是为了排除那些既有左右子节点又有根节点的情况。

需要注意的是，这里的递归实现并不是最有效的方式。由于只有当当前节点是叶子节点时，其左子树和右子树才会被访问，因此我们可以提前终止递归过程。这种优化可以显著提高程序性能，尤其是在处理大型数据集时。

以下是优化后的代码：

int CountNode_Leaf(pBTNode t, int leaf_count)
{
    if (!t) return leaf_count; // 如果当前节点为空，则直接返回已经计算好的叶节点总数

    int l = CountNode_Leaf(t->LTree, leaf_count); // 计算左子树中的叶节点数量
    int r = CountNode_Leaf(t->RTree, leaf_count); // 计算右子树中的叶节点数量

    // 当前节点是叶子节点，将其加入总数中
    if (t->LTree && t->RTree) {
        leaf_count++;
    }

    return l + r + 1; // 返回当前节点的叶节点数量
}

现在，这个优化后的版本应该能够更有效地计算出二叉树中的叶子节点数量。