第24章树形结构的递归算法

课程目录第24章树形结构的递归算法

24、树形结构的递归算法：递归遍历的深入理解、递归求树的高度、递归求树的宽度

树形结构，说白了就是递归的天然载体。你想想看，一棵树的每个子树，它本身也是一棵树。这种「自相似」的特性，让递归算法成了处理树结构最趁手的工具。我个人习惯，拿到一个树的问题，第一反应就是：能不能用递归拆解？

今天咱们就深入聊聊递归遍历、递归求树的高度和宽度。这三个问题，是树形结构递归算法的基本功，也是面试里高频出现的考点。

递归遍历的深入理解

先说说遍历。二叉树的遍历有四种：前序、中序、后序、层序。前三种天然适合递归，层序一般用队列迭代。

递归遍历的核心就一句话：访问根节点 + 递归遍历左子树 + 递归遍历右子树。顺序不同，遍历方式就不同。

// 前序遍历：根 -> 左 -> 右
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);   // 访问根
    preOrder(root->left);       // 遍历左
    preOrder(root->right);      // 遍历右
}

// 中序遍历：左 -> 根 -> 右
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}

// 后序遍历：左 -> 右 -> 根
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->val);
}

代码看着简单，但很多人写的时候容易犯一个错：递归终止条件写不对。我曾经在代码审查里见过一个同事，递归遍历时忘了判断 root == NULL，结果栈溢出，程序直接崩了。嗯，这个坑一定要记住。

注意：递归遍历的终止条件必须是 root == NULL。不要写成 root->left == NULL && root->right == NULL，那样会漏掉只有一个子节点的节点。

递归遍历的「深入理解」，其实在于理解递归栈的变化。每次递归调用，系统会把当前函数的局部变量、参数、返回地址压入栈中。当递归返回时，再从栈中弹出。你想想看，前序遍历是先访问根，再递归左子树，所以根节点最先被访问。中序遍历是先递归左子树，再访问根，所以根节点在中间被访问。后序遍历则是最后访问根。

这个顺序，说白了就是「什么时候处理根节点」的问题。

递归求树的高度

树的高度，也叫深度。从根节点到最远叶子节点的路径长度。递归求高度的思路很直接：树的高度 = max(左子树高度, 右子树高度) + 1。

int treeHeight(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

这个代码，我建议你背下来。不是死记硬背，而是理解它的递归逻辑。空树高度为0，这是递归基。非空树的高度，等于左右子树中较高的那个再加1。

我在项目中遇到过一个问题：求树的高度时，把空树的高度返回成了-1。结果后续所有计算都偏移了1。后来排查了半天才发现是递归基写错了。所以，递归基一定要想清楚。

小技巧：如果你不确定递归基对不对，可以画一棵只有根节点的树，手动模拟一下递归过程。根节点左右子树都为空，递归调用返回0，然后取max(0,0)+1=1。高度为1，正确。

递归求树的宽度

树的宽度，指的是某一层上节点数的最大值。求宽度比求高度要复杂一些，因为需要统计每一层的节点数。

递归求宽度的思路：先求出树的高度，然后遍历每一层，统计该层的节点数，取最大值。

// 统计第k层的节点数
int countNodesAtLevel(TreeNode* root, int k) {
    if (root == NULL) return 0;
    if (k == 1) return 1;
    return countNodesAtLevel(root->left, k-1) + 
           countNodesAtLevel(root->right, k-1);
}

// 求树的宽度
int treeWidth(TreeNode* root) {
    int h = treeHeight(root);
    int maxWidth = 0;
    for (int i = 1; i <= h; i++) {
        int width = countNodesAtLevel(root, i);
        if (width > maxWidth) maxWidth = width;
    }
    return maxWidth;
}

这个算法的时间复杂度是O(n²)，因为每层都要遍历一次整棵树。如果树很大，效率不高。但作为递归练习，它很经典。

我曾经在优化一个树形结构的渲染引擎时，需要频繁计算树的宽度。用这个递归方法，树深了之后性能很差。后来改成了层序遍历（BFS），用队列一次遍历就统计出所有层的节点数，时间复杂度降到了O(n)。

  核心要点：递归求宽度虽然直观，但效率不高。实际项目中，如果树比较大，建议用层序遍历替代。但面试时，递归解法更容易展示你对递归的理解。

知识体系总览

下面这张图，把递归遍历、求高度、求宽度的核心逻辑串起来了。你可以对照着看，理解它们之间的关系。

递归算法的三个关键点

写递归算法，我总结了三个关键点，你写的时候可以对照着检查：

递归基要明确：什么情况下递归停止？空树？叶子节点？一定要想清楚。
递归调用要正确：参数怎么传？返回值怎么处理？调用顺序对不对？
结果合并要合理：子问题的结果怎么组合成原问题的结果？是取最大值、求和、还是拼接？

这三个点，说白了就是「什么时候停、怎么往下走、回来怎么处理」。你写递归的时候，脑子里过一遍这三个问题，基本不会出错。

我的习惯：写递归函数之前，先在注释里把递归基和递归逻辑写清楚。比如：
// 递归基：root == NULL 返回0
// 递归逻辑：左子树高度 + 右子树高度 + 1
这样写代码的时候思路清晰，不容易漏掉边界情况。

避坑指南

最后，分享几个我踩过的坑：

栈溢出：树太深的时候，递归调用层数太多，会栈溢出。我曾经在处理一个深度为10000的树时，程序直接崩溃。后来改成了迭代法才解决。
重复计算：递归求宽度时，每层都遍历整棵树，重复计算严重。如果树很大，性能会非常差。
递归基写错：比如求高度时，把空树的高度返回成-1，或者把叶子节点的高度返回成0。这些细节很容易出错。

嗯，递归这东西，说白了就是「用空间换时间」——用函数调用栈的空间，换取代码的简洁和可读性。理解透了，你会发现树形结构的很多问题，用递归解决都特别自然。

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

📚 课程目录

24、树形结构的递归算法：递归遍历的深入理解、递归求树的高度、递归求树的宽度

递归遍历的深入理解

递归求树的高度

递归求树的宽度

知识体系总览

递归算法的三个关键点

避坑指南