二叉树系列之递归

引言

首先我们需要知道，二叉树非常适合递归处理，因为二叉树本身就是递归定义的：

• 每个节点最多有两个子节点（左子树、右子树）
• 每个子树本身又是一棵二叉树
• 空树也是二叉树的一种情况（递归的终止条件）

此外，二叉树问题可以自然地分解为处理该节点与其左右子树的问题

递归问题需要注意以下三点：

• 递归终止条件：什么时候停止递归
• 递归逻辑：如何处理当前节点
• 返回值：向上一层返回什么

接下来我会列出一些我自己在写力扣的时候遇到的部分题目

---

二叉树的中序遍历

LeetCode 94. 二叉树的中序遍历

问题描述

给定一个二叉树的根节点 root ，返回它的 中序遍历

递归思路

中序遍历的顺序是：左子树 → 根节点 → 右子树

void inorder(struct TreeNode* root,int* num,int* ret){
    if(root==NULL)
    return;
    inorder(root->left,num,ret);
    ret[(*num)++]=root->val;
    inorder(root->right,num,ret);    
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *re =(int *)malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root,returnSize,re);
    return re;
}

这里有一点我一开始没注意，就是传入的 returnSize 其实是一个指针，在使用inorder函数时不需要 & 符号，直接传入 returnSize 即可

---

二叉搜索树中第K小的元素

LeetCode 230. 二叉搜索树中第K小的元素

问题描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小的元素

递归思路

利用BST中序遍历有序性，递减k计数，提前返回进行优化

代码实现

void kFind(struct TreeNode* root, int* k, int* result){
    if(root == NULL || *k == 0)//方便提前返回
        return;
    
    kFind(root->left, k, result);
    
    (*k)--;
    if(*k == 0){
        *result = root->val;
        return;
    }
    
    kFind(root->right, k, result);
}

int kthSmallest(struct TreeNode* root, int k) {
    int result = -1;
    kFind(root, &k, &result);
    return result;
}

这里在kFind函数中增加了一个提前返回的条件，当*k == 0时，说明已经找到了第k小的元素，可以直接返回，避免不必要的递归调用

---

对称二叉树

LeetCode 101. 对称二叉树

问题描述

给你一个二叉树的根节点 root ， 检查它是否轴对称

递归思路

递归判断镜像，左子树的左孩子与右子树的右孩子对比

代码实现

bool isMirror(struct TreeNode* left, struct TreeNode* right){
    if(!left&&!right)
    return true;
    if(!left||!right)
    return false;
    if(left->val!=right->val)
    return false;
    return isMirror(left->left,right->right)&&isMirror(left->right,right->left);
} 
bool isSymmetric(struct TreeNode* root) {
    if(root==NULL)
    return true;
    return isMirror(root->left,root->right);
}

本题的思路还与一题判断两颗二叉树是否相同类似，不过那一题在递归传递参数时传递的是root1的左和root2的左，而本题传递的是root的左和root的右

---

二叉树的最大深度

LeetCode 104. 二叉树的最大深度

问题描述

给定一个二叉树的根节点 root ，返回其最大深度

递归思路

自底向上递归，depth = max(leftDepth, rightDepth) + 1

代码实现

int maxDepth(struct TreeNode* root) {
    if(root==NULL)
    return 0;
    int lmax = maxDepth(root->left);
    int rmax = maxDepth(root->right);
    return(lmax>rmax?lmax:rmax)+1;
}

本题是典型的自底向上递归，先计算左右子树的最大深度，然后取较大值加一返回

---

二叉树的直径

LeetCode 543. 二叉树的直径

问题描述

给定一棵二叉树，你需要计算它的直径长度。二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过根节点

递归思路

通过递归计算二叉树的最大深度，同时更新树的直径（即任意两个节点之间的最长路径）,最大深度函数返回左右子树深度的较大值，并更新全局最大路径值

代码实现

int maxDepth(struct TreeNode* root,int* maxl){
    if(root==NULL)
    return 0;
    int lmax=maxDepth(root->left,maxl);
    int rmax=maxDepth(root->right,maxl);
    *maxl=fmax(*maxl,lmax+rmax);
    return fmax(lmax,rmax)+1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
    if(root==NULL)
    return 0;
    int maxl=0;
    maxDepth(root,&maxl);
    return maxl;
}

在maxDepth函数中，我们计算左右子树的深度，并更新*maxl为当前的最大直径。最终在diameterOfBinaryTree函数中返回这个最大直径值

---

翻转二叉树

LeetCode 226. 翻转二叉树

问题描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

递归思路

递归交换每个节点的左右子节点

代码实现

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    invertTree(root->left);
    invertTree(root->right);
    
    return root;
}

交换当前节点的左右子节点，接着递归调用invertTree函数来翻转左右子树,最后返回翻转后的根节点

---

二叉树的最近公共祖先

LeetCode 236. 二叉树的最近公共祖先

问题描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先节点

递归思路

递归遍历树，判断当前节点是否为p或q，若是则返回当前节点，否则递归左右子树，若左右子树均返回非空节点，则当前节点即为最近公共祖先

代码实现

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root; // 找到 p 或 q 就不往下递归了
    }
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) { // 左右都找到
        return root; // 当前节点是最近公共祖先
    }
    // 如果只有左子树找到，就返回左子树的返回值
    // 如果只有右子树找到，就返回右子树的返回值
    // 如果左右子树都没有找到，就返回 NULL（注意此时 right = NULL）
    return left ? left : right;
}

这里的关键在于递归返回值的处理，通过判断左右子树的返回值来确定当前节点是否为最近公共祖先，像本题我们就要注意是后序遍历，因为这里我们需要左右子树的结果来决定当前节点的返回值

---

二叉树展开为链表

LeetCode 114. 二叉树展开为链表

问题描述

给你二叉树的根节点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个节点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历顺序相同。

递归思路

本题要求与先序遍历顺序相同，这里可以采用头插法，按照先序的逆序（右-左-根）来处理节点，即先处理右子树，再处理左子树，这样在构建链表时就能保证顺序正确

代码实现

void dfs(struct TreeNode* node, struct TreeNode** head) {
    if (node == NULL) {
        return;
    }
    dfs(node->right, head);
    dfs(node->left, head);
    node->left = NULL;
    node->right = *head; // 头插法，相当于链表的 node->next = head
    *head = node; // 现在链表头节点是 node
}

void flatten(struct TreeNode* root) {
    struct TreeNode* head = NULL;
    dfs(root, &head);
}

在dfs函数中，我们先递归处理右子树，再处理左子树，这样可以确保我们按照先序遍历的顺序构建链表，通过头插法，我们将当前节点的右指针指向链表的头节点，并更新头节点为当前节点，最终实现了二叉树的展开为链表

---

深入理解：二叉树递归顺序的选择

一、核心本质：二叉树递归 = 在”什么时候”处理当前节点

任何二叉树递归，本质都是这三步的排列组合：

• dfs(node->left);
• 处理当前节点;
• dfs(node->right);

不同的递归顺序，本质区别在于：你希望在什么时候处理当前节点

递归顺序	处理节点的时机	本质含义
前序	先处理自己，再处理子树	自顶向下
中序	左子树后、右子树前	与结构强相关
后序	子树都处理完再处理自己	自底向上

---

二、不同递归顺序一般对应什么题目？

① 前序遍历（根 → 左 → 右）

特点：先用当前节点的信息，再递归子树

适合的题目类型

“当前节点会影响子节点” 的问题

典型特征：

• 父节点的信息要传递给子节点
• 路径类问题
• 从根向下的构造、记录、判断

常见题目

• 路径和（Path Sum）
• 根到叶子的路径
• 验证 BST（携带 min/max）
• 树的序列化
• 建树（根据遍历）

思维模板

“我要先知道当前节点是什么，再决定怎么走下去”

---

② 中序遍历（左 → 根 → 右）

特点：节点处理夹在左右之间

适合的题目类型

和”顺序””结构”强相关的题目，尤其是 BST（搜索二叉树）

常见题目

• 验证 BST（中序是否有序）
• BST 转数组
• 第 k 小元素
• BST 相关统计

思维模板

“左边处理完，当前节点才有意义”

---

③ 后序遍历（左 → 右 → 根）

特点：先拿到子树结果，再处理当前节点

适合的题目类型

“当前节点的结果依赖子树”

常见题目

• 最大深度 / 最小深度
• 直径
• 是否平衡二叉树
• 最大路径和
• 翻转 / 删除 / 合并子树
• flatten（二叉树展开）

思维模板

“我得先知道左右子树情况，才能算我自己”

---

三、核心判断技巧：三问法

看到一个二叉树递归题，先别写代码，先问自己这三个问题：

问题 1：当前节点的结果，依赖谁？

依赖对象	选择顺序
依赖父节点	前序
依赖左右子树	后序
依赖结构顺序	中序

问题 2：是”向下传信息”，还是”向上汇总信息”？

信息流方向	顺序
从根到叶子	前序
从叶子到根	后序

问题 3：递归函数”返回值”代表什么？

这是决定后序遍历的最重要信号

如果递归函数有明确的返回值含义，且这个返回值用于父节点计算

大概率是后序遍历

---

四、总结要点

1. 前序 = 自顶向下传递信息（父节点影响子节点）
2. 中序 = BST 相关（利用中序遍历的有序性）
3. 后序 = 自底向上汇总信息（子树结果影响父节点）