6-45 calculating the number of leaves of a binary tree

This problem is to calculate the number of leaf nodes in a binary tree .

Function interface definition ：

 The function interface is described here . for example ：
int num (Bptr p);

Sample referee test procedure ：

#include <stdio.h>
#include <malloc.h>
typedef struct node
{
    int data;
    struct node *Lson,*Rson;
}Bnode,*Bptr;

int num (Bptr p);

Bptr creat()
{
    Bptr p;
    int x;
    scanf("%d",&x);
    if(x==0)
        return NULL;
    p=(Bptr)malloc(sizeof(Bnode));
    p->data=x;
    p->Lson=creat();
    p->Rson=creat();
    return p;
}

int main()
{
  Bptr root;    
    int k;    
    root=creat();
  k=num(root);
  printf("%d\n", k);
  return 0;

}

/*  Please fill in the answer here  */

sample input ：

3 4 1 0 0 0 2 0 0

sample output ：

2

  Ideas ： This problem requires us to calculate the number of leaves of a binary tree , that How to calculate ？ First, we need to traverse the binary tree , Then look for the leaves of the binary tree . that , How do we judge whether it is a leaf node ？ According to the definition of leaf node , As long as the left and right sons of the node are empty, we can judge whether the node is a leaf ！ good , The conditions are , The number of leaves ？ Here I have two ideas , One is that we set a count variable , For example count=0, Every time we traverse to a leaf node ,count Just +1; The other is , Suppose the traversal function is fun(), Then we go back , For example, matching to a node , We remember that 1, And then through fun(p->Lson)+fun(p->Rson) In this way, the number of leaf nodes is recursively returned , In this way, the final result is the number of leaf nodes , Don't talk much , Code up ：
The first way ：

int num(Bptr p) {
	int count = 0;// Set calculation variables 
	if (p->Lson==NULL && p->Rson==NULL ) // Judge whether the current node is a leaf node 
		return 1;
	if (p->Lson)  // Determine whether the left son of the node exists 
		count+= num(p->Lson);
	if(p->Rson) // Determine whether the right son of the node exists 
		count+= num(p->Rson);
	return count;// Returns the number of leaf nodes 
}

The second way ：

int num(Bptr p) {
    if (p == NULL)// Judge whether the root node is empty 
    {
        return 0;// Notice that this is 0 instead of 1 Oh 
    }
    if (p->Lson == NULL && p->Rson == NULL)// Judge whether it is a leaf node 
    {
        return 1;
    }
    return num(p->Lson)+num(p->Rson);// Returns the number of leaf nodes 
  
}

remind ： In the second way, I will explain why I am p==NULL When to return to 0 instead of 1 Well ？ Here we can think so , Suppose we have only one root node , So are its left and right sons empty , At this time it satisfies the first regulation , But it also meets the second condition , So if our first condition returns 1 Words , Whether the number of leaf nodes output here is 2 了 ？ To avoid repetition , So we can only return to this place 0