C语言递归计算二叉树的深度和叶子结点的个数算法分析

递归计算二叉树的深度和叶子结点的个数是二叉树常见的算法之一。

算法思路如下：

1. 判断当前节点是否为空，如果为空，则返回0

2. 递归计算左子树的深度和叶子结点个数

3. 递归计算右子树的深度和叶子结点个数

4. 返回左右子树深度较大值加1，叶子结点个数相加的结果

具体的C语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 计算二叉树深度和叶子结点个数
void calDepthAndLeaf(TreeNode* root, int* depth, int* leaf) {
    if (root == NULL) {
        *depth = 0;
        *leaf = 0;
        return;
    }
    int leftDepth, leftLeaf, rightDepth, rightLeaf;
    calDepthAndLeaf(root->left, &leftDepth, &leftLeaf);
    calDepthAndLeaf(root->right, &rightDepth, &rightLeaf);
    *depth = (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    *leaf = leftLeaf + rightLeaf;
    if (root->left == NULL && root->right == NULL) {
        *leaf += 1;
    }
}

int main() {
    // 构造一棵二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    int depth, leaf;
    calDepthAndLeaf(root, &depth, &leaf);
    printf("二叉树的深度为：%d\n", depth);
    printf("二叉树的叶子结点个数为：%d\n", leaf);

    return 0;
}

以上代码中，我们测试了一棵如下的二叉树：

      1
     / \
    2   3
       / \
      4   5

运行结果如下：

二叉树的深度为：3
二叉树的叶子结点个数为：3

可以看出，我们的代码计算出了该二叉树的深度和叶子结点个数。