第14章递归与树

课程目录第14章递归与树

递归与树：二叉树的深度、节点个数、叶子节点个数

树结构，说白了就是递归的天然载体。你想想看，一棵树的每个节点下面又是一棵子树，这不就是「自己调用自己」的完美映射吗？我在项目中处理文件系统目录树时，就深刻体会到了这一点——目录套目录，用递归遍历简直不要太顺手。

今天咱们就聚焦二叉树，用递归来解决三个经典问题：树的深度、节点总数、叶子节点个数。这三个问题看似简单，但它们是理解树递归的基石。

1. 二叉树的结构定义

先看看二叉树长什么样。每个节点有数据域、左孩子指针、右孩子指针：

typedef struct TreeNode {
    int data;                 // 数据域
    struct TreeNode *left;    // 左孩子
    struct TreeNode *right;   // 右孩子
} TreeNode;

嗯，这里要注意：left 和 right 本身就是指向子树的指针，而子树的结构和父节点一模一样。这就是递归的「结构自相似性」。

2. 二叉树的深度（最大高度）

树的深度，就是从根节点到最远叶子节点的路径长度。怎么算？

我个人的习惯是这么想的：一棵树的深度 = max(左子树深度, 右子树深度) + 1。空树的深度为0。

看代码：

int treeDepth(TreeNode *root) {
    if (root == NULL) {
        return 0;  // 空树，深度为0
    }
    int leftDepth = treeDepth(root->left);
    int rightDepth = treeDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

逻辑很直白：先问左子树多深，再问右子树多深，取较大的那个，加上自己这一层。

小提示：递归的「信任」很重要。你不需要手动模拟递归栈的每一层，你只需要相信：treeDepth(root->left) 一定能正确返回左子树的深度。这就是递归的「信仰之跃」。

3. 二叉树的节点个数

数节点个数，思路类似：总节点数 = 左子树节点数 + 右子树节点数 + 1（根节点自己）。

int countNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

我曾经在面试中遇到过候选人，写递归时总喜欢加一个全局变量来计数。其实没必要——递归的返回值本身就是天然的计数器。你想想看，每次调用返回的是「以当前节点为根的子树节点数」，层层累加，最终就是整棵树的节点数。

4. 叶子节点个数

叶子节点，就是没有孩子的节点（左右孩子都为NULL）。判断条件很直接：

int countLeaves(TreeNode *root) {
    if (root == NULL) {
        return 0;  // 空树，没有叶子
    }
    // 如果左右孩子都为空，说明是叶子节点
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    // 否则，叶子数 = 左子树叶子数 + 右子树叶子数
    return countLeaves(root->left) + countLeaves(root->right);
}

这里有个细节：空树返回0，叶子节点返回1，内部节点继续递归。三种情况，三种处理，清晰明了。

避坑指南：我曾经在写叶子节点计数时，忘记处理空树的情况，结果传入NULL时程序直接崩溃。记住：任何递归函数，必须先处理「最小子问题」——也就是空节点的情况。这是递归的「终止条件」，漏了它，递归就变成了死循环。

5. 知识体系总览

下面这张图，把三个问题的递归逻辑串在了一起：

6. 完整示例代码

把三个函数整合到一起，写个测试：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 树的深度
int treeDepth(TreeNode *root) {
    if (root == NULL) return 0;
    int left = treeDepth(root->left);
    int right = treeDepth(root->right);
    return (left > right ? left : right) + 1;
}

// 节点个数
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

// 叶子节点个数
int countLeaves(TreeNode *root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
    // 构建一棵简单的二叉树：
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    
    printf("树的深度: %d\n", treeDepth(root));       // 输出 3
    printf("节点个数: %d\n", countNodes(root));      // 输出 5
    printf("叶子节点个数: %d\n", countLeaves(root)); // 输出 3（节点3、4、5）
    
    return 0;
}

7. 递归的「三板斧」

总结一下，写树递归其实就三步：

终止条件：空树怎么办？叶子节点怎么办？
递归分解：左子树和右子树分别调用自身。
结果合并：左右子树的结果如何组合成当前节点的结果？

这三个问题，深度是「取最大值+1」，节点数是「求和+1」，叶子数是「求和（叶子返回1）」。你看，结构一模一样，只是合并逻辑略有不同。

核心心法：写递归时，别想着「计算机是怎么执行的」，而是想「这个问题的数学定义是什么」。树的深度、节点数、叶子数，都有明确的数学递推关系。你把递推关系写成代码，递归自然就对了。

好了，今天的内容就到这里。二叉树递归的三个经典问题，说白了就是「分而治之」思想的体现。下次遇到树的问题，先问自己三个问题：终止条件是什么？如何分解？如何合并？答案自然就有了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

递归与树：二叉树的深度、节点个数、叶子节点个数

1. 二叉树的结构定义

2. 二叉树的深度（最大高度）

3. 二叉树的节点个数

4. 叶子节点个数

5. 知识体系总览

6. 完整示例代码

7. 递归的「三板斧」