java - 计算Java中二叉树中的叶节点

Question

我写了下面的代码来查找二叉树中叶节点的数量。我在 GeeksForGeeks 上提交了它，它给出了正确答案的结果，但我不确定他们是否已经检查过大量测试用例。你能告诉我这是否是正确的解决方案吗？

int sum=0;
int countLeaves(Node node) 
{
     // Your code
     if(node==null)
     return sum;
     if(node.left!=null || node.right!=null)
     {
         sum=countLeaves(node.left);
         sum=countLeaves(node.right);
     }
     else
     {
         sum++;
     }
     return sum;

}

Answer 1

您的解决方案似乎确实产生了正确的结果，但它以一种笨拙的方式产生了。将 countLeaves(node.left) 和 countLeaves(node.right) 分配给 sum 乍一看就像一个错误。乍一看，这完全没有必要，因为 sum 已经包含您分配给它的值。

如果您使用外部变量 (sum) 来计算叶子数量(这通常是个坏主意)，则将递归调用的结果分配给 sum< 是没有意义的.

你可以简单地写:

int sum=0;
int countLeaves(Node node) 
{
     if(node==null)
         return sum;
     if(node.left!=null || node.right!=null) {
         countLeaves(node.left);
         countLeaves(node.right);
     } else {
         sum++;
     }
     return sum;
}

您甚至可以将该方法更改为不返回任何内容，并在调用后从 sum 变量中获取结果。

但是，我建议避免使用 sum 变量，以使代码更清晰:

int countLeaves(Node node) 
{
    if (node==null)
        return 0;
    else if (node.left!=null || node.right!=null) {
        return countLeaves(node.left) + countLeaves(node.right);
    } else {
        return 1;
    }
}