java - 在没有给定参数的情况下递归计算二叉树中的叶子数

Question

我正在努力弄清楚如何编写递归算法来计算二叉树(不是完整树)中叶子的数量。我走到最左边的叶子，不知道从那里返回什么。我试图通过将叶子加载到列表中并获取该列表的大小来获取计数。这可能是一种糟糕的计数方式。

    public int countLeaves ( ) {

    List< Node<E> > leafList = new ArrayList< Node<E> >();
    //BinaryTree<Node<E>> treeList = new BinaryTree(root);

    if(root.left != null) 
    {
        root = root.left;
        countLeaves();
    }
    if(root.right != null) 
    {
        root = root.right;
        countLeaves();
    }
    if(root.left == null && root.right == null) 
    {
        leafList.add(root);
    }


        return();
}

Answer 1

详细阐述@dasblinkenlight 的想法。您想要递归调用根节点上的计数叶并将 # 传回给调用者。以下几行内容。

public int countLeaves() {
 return countLeaves(root);
 }

/**
 * Recursively count all nodes
 */
private static int countLeaves (Node<E> node) {
 if(node==null)
   return 0;

 if(node.left ==null && node.right == null)
  return 1;
 else {
    return countLeaves(node.left) + countLeaves(node.right);
   }
}

编辑:看来，之前有人问过类似的问题counting number of leaf nodes in binary tree