求统计二叉树叶子结点数的递归算法

算法思想：

对每个节点来说：

1、如果它没有子节点，那么它就是叶子节点。

2、如果它有子节点，那么它的叶子节点数量 = 左子树叶子节点数量 + 右子树叶子节点数量。

算法代码：

unsigned int getLeafCount(struct node* node)
{
  if(node == NULL)      
    return 0;
  if(node->left == NULL && node->right==NULL)     
    return 1;           
  else
    return getLeafCount(node->left)+
           getLeafCount(node->right);     
}

时间复杂度：O(n)，空间复杂度：O(n)

---------------------------------------------------

附上一个例子：

#include 
#include 
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
 
/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
  if(node == NULL)      
    return 0;
  if(node->left == NULL && node->right==NULL)     
    return 1;           
  else
    return getLeafCount(node->left)+
           getLeafCount(node->right);     
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
   
  return(node);
}
 
/*Driver program to test above functions*/ 
int main()
{
  /*create a tree*/ 
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);   
   
  /*get leaf count of the above created tree*/
  printf("Leaf count of the tree is %d", getLeafCount(root));
   
  getchar();
  return 0;
}

void dfs(int x)
{
    if(a[x].l==0&&a[x].r==0)//如果到达叶子节点，即没有左右儿子，累加答案ans，递归回父亲
    {
        ans++;
        return;
    }
    if(a[x].l) dfs(a[x].l);//有左儿子，下去找
    if(a[x].r) dfs(a[x].r);//有右儿子，下去找
}

手写的，可能有误，请谅解。

PS:a[i].l为i的左儿子，a[i].r为i的右儿子

//默认使用C语言编程。

//二叉树定义：
struct BNode{
    int value;
    Bnode* left, right;
} root;

//返回页结点个数的函数：
int get_leaf_num(Node* root)
{
    if( root -> left == NULL && root -> right == NULL)
    {
        return 1;
    }
    else if( root -> left == NULL)
    {
        return get_leaf_num( root -> right );
    }
    else if( root -> right == NULL)
    {
        return get_leaf_num( root -> left );
    }
    else
    {
        return get_leaf_num( root -> left) + get_leaf_num( root -> right);
    }
}

public static int numOfLeavesInRecursion(BinaryTreeNode root){ // 获取二叉树叶子节点的个数的递归算法

if(root == null)

return 0;

if(root.getLeft() == null && root.getRight() == null)

return 1;

return numOfLeavesInRecursion(root.getLeft())+
numOfLeavesInRecursion(root.getRight());

}

不知道你要用什么语言，猜你是在学数据结构就用C吧
int Nodes(Tree T)
{

int count;
if(T==NULL) //空树
count=0;
else if(T->Lchild==NULL&&T->Rchild==NULL) //只有一个节点
count=1;
else
count=Nodes(T->Lchild)+Nodes(T->Rchild);
return count;
}