java - 递归计算二叉树中的叶子数

Question

ALGORITHM LeafCounter(BTNode node) 
  // Computers recursively the number of leaves in a binary tree
  // Input: Root node of a binary (sub-)tree 1/ 
  // Output: The number of leaves in the tree rooted by input node
  if (node == null) return 0;
  else 
    return LeafCounter(node.getLeftChild 0 ) + Leaf Counter(node.getRightChild();

我不确定如何编辑它，以便准确计算叶子？此外，如果您能提供失败原因的证据，这对我来说将非常有帮助，看起来它应该可以工作

Answer 1

正确的算法：

ALGORITHM LeafCounter(BTNode node) 
  // Computers recursively the number of leaves in a binary tree
  // Input: Root node of a binary (sub-)tree 1/ 
  // Output: The number of leaves in the tree rooted by input node
  if (node == null) return 0;
  else 
    //Since current node is not null so 
    return 1 + LeafCounter(node.getLeftChild()) + Leaf Counter(node.getRightChild());

注意：您可能需要从最终结果中减去 1，以从计数中排除根节点。

Answer 2

您只需要检查叶子状况，即可给出正确的结果。

ALGORITHM LeafCounter(BTNode node) 
  // check base condition
  if (node == null) return 0;
  // check leaf condition
  if (node.getLeftChild() == null && node.getRightChild() == null) return 1;
  // recurse for children
  else return LeafCounter(node.getLeftChild()) + LeafCounter(node.getRightChild());