algorithm - 计算深度的二叉树叶子

Question

我正在尝试创建一个函数来计算从根节点开始指定级别的树的叶子数。

意思是我有一个函数 leafcount(BTNode node, int level)

为如下所示的树结构调用此函数 leafCount(root,2) 应该产生 1，即它从根计算第 2 层的叶节点 B。它忽略其他叶 C，因为它不在 level 2 而在 level 1

        root
       /    \
      A      C 
     /
    B

我尝试使用递归实现以下

int leafCount(BTNode node, int level){

if(node == null){
 return 0;
}
if(level == 0 && (node.left == null && node.right == null)){
 return 1;
}
else{
 return leafCount(node.left,level--) + leafCount(node.right,level--);
}

虽然没用。我做错了什么？

Answer 1

您正在通过放置 level-- 使用后递减运算符。所以 level-- 发生在函数调用之后而不是之前。如果您更改为预递减 --level，您也会将级别递减两次。只需将 level-- 作为一行代码放在递归函数调用之上一次，然后将 level 传递给函数调用。此外，如果 level == 0 您可以返回 0 或 1 而无需探索节点下方树的其余部分。如果您的树比您想要在其上查找叶子的所需级别深得多，这将稍微加快搜索速度。