核心：递归是通过函数自我调用，将大问题分解为同类子问题来求解的算法思想，配合数学归纳法和栈结构理解递归的正确性和执行过程。
一、基础知识点
1. 递归入门：二叉树的最大深度 💡
题目描述
给定一棵二叉树，求其最大深度。最大深度定义为根节点到最远叶子节点的最长路径上的节点数。
核心概念
什么是递归？
递归就是函数自己调用自己，通过不断 "递"（分解问题）和 "归"（返回结果）来解决问题。
为什么用递归？
循环是重复执行同一份代码，每次操作的是同一个变量。递归处理的是有嵌套关系的问题，子问题的结果需要返回给上一级。子问题和原问题具有相同的结构，可以用同一份代码解决。
递归的两个必要条件
边界条件（终止条件）：递归要有尽头，否则会无限循环。在二叉树中，边界条件就是空节点 None。
递归调用：把问题分解成更小的同类子问题。最大深度 = max(左子树深度, 右子树深度) + 1
算法步骤
以计算二叉树最大深度为例：
明确边界条件：节点为空，返回 0
分解子问题：递归计算左子树的最大深度、递归计算右子树的最大深度
合并结果：返回 max(左子树深度, 右子树深度) + 1
图解过程
3
/ \
9 20
/ \
15 7
递的过程：
3 → 9(左子树) → None → 返回 0
3 → 20(右子树) → 15(左子树) → None → 返回 0
20 → 7(右子树) → None → 返回 0
归的过程：
9: max(0, 0) + 1 = 1
15: max(0, 0) + 1 = 1
7: max(0, 0) + 1 = 1
20: max(1, 1) + 1 = 2
3: max(1, 2) + 1 = 3
为什么递归是对的？（数学归纳法）
递归的正确性可以用数学归纳法证明：
基础情况（n=0）：空节点的深度为 0，这是正确的
归纳假设：假设递归计算左子树和右子树的深度是正确的
归纳步骤：整棵树的深度 = max(左子树, 右子树) + 1，这是正确的
计算机如何执行递归？（栈）
递归调用时，计算机会用 ** 栈（Stack）** 来保存每一层的信息。递的过程：每进入一层递归，就把当前节点入栈。归的过程：每返回一层，就把栈顶节点出栈，继续返回。
# 栈的变化过程
递: 3 → 9 → None(空节点，返回)
归: 9 ← 0
递: 3 → 20 → 15 → None
归: 15 ← 0, 20 ← 1
递: 3 → 20 → 7 → None
归: 7 ← 0, 20 ← 2, 3 ← 3
Python 实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root: TreeNode) -> int:
# 边界条件：空节点返回 0
if root is None:
return 0
# 递归计算左子树深度
left_depth = maxDepth(root.left)
# 递归计算右子树深度
right_depth = maxDepth(root.right)
# 返回较大值 + 1（加上当前节点）
return max(left_depth, right_depth) + 1
复杂度
时间：O(n)，每个节点遍历一次
空间：O(h)，h 为树的高度，栈的深度等于树的高度
特殊情况的边界分析
2. 递归的另一种形式：维护全局状态 ✨
核心思想
在递归过程中，除了传递节点信息，还可以传递路径上的累计值，并用全局变量维护答案。
算法步骤
初始化全局变量
ans = 0递归函数传入
node和count（当前路径的节点数）每到达一个节点，
count += 1，更新ans继续递归左右子树
遍历完成后，
ans即为最大深度
Python 实现
def maxDepth(root: TreeNode) -> int:
ans = 0 # 全局变量，保存最大深度
def dfs(node, count):
nonlocal ans # 在 Python 中修改外部变量需要声明
if node is None:
return
count += 1 # 到达新节点，路径长度 +1
ans = max(ans, count) # 更新最大深度
dfs(node.left, count) # 递归左子树
dfs(node.right, count) # 递归右子树
dfs(root, 0)
return ans
二、练习
1. 二叉树的最小深度 🔢
题目描述（LeetCode 111 - 简单）
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例
输入：root = [3,9,20,null,null,15,7]
输出：2
3
/ \
9 20
/ \
15 7
根节点到最近叶子节点的路径：3 → 9，长度为 2
解题思路
最小深度和最大深度的区别在于：最小深度必须是根节点到叶子节点的路径。
如果一个节点只有左子树或只有右子树，不能用 max(left, right) + 1，而应该用非空子树的结果。只有左右子树都不为空时，才取最小值。
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
# 只有右子树，返回右子树的最小深度 + 1
if root.left is None:
return self.minDepth(root.right) + 1
# 只有左子树，返回左子树的最小深度 + 1
if root.right is None:
return self.minDepth(root.left) + 1
# 左右子树都有，取较小值 + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
复杂度
时间：O(n)
空间：O(h)
2. 左叶子之和 📐
题目描述（LeetCode 404 - 简单）
给定二叉树的根节点 root ，返回所有左叶子之和。
示例
输入：root = [3,9,20,null,null,15,7]
输出：24
解释：在这个二叉树中，有两个左叶子（9 和 15），所以返回 24
3
/ \
9 20
/ \
15 7
解题思路
如何判断一个节点是左叶子？ 它是某个节点的左子节点，同时它本身没有左右子节点（是叶子节点）。
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
# 递归计算左右子树的左叶子之和
ans = self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
# 检查左子节点是否是叶子节点
left = root.left
if left and left.left is None and left.right is None:
ans += left.val # 累加左叶子的值
return ans
复杂度
时间：O(n)
空间：O(h)
3. 路径总和 🎯
题目描述（LeetCode 112 - 简单）
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
示例
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示：5 → 4 → 11 → 2 = 22
解题思路
自顶向下的递归：从根节点出发，逐步减去经过的节点值，判断是否能恰好减到 0。
每递归一层，targetSum 减去当前节点的值。如果到达叶子节点且 targetSum 变为 0，说明找到目标和。用 or 逻辑，只要左子树或右子树有一条路径满足即可。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
# 减去当前节点的值
targetSum -= root.val
# 到达叶子节点，判断是否恰好为 0
if root.left is None and root.right is None:
return targetSum == 0
# 递归检查左右子树，只要有一条路径满足即可
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
复杂度
时间：O(n)
空间：O(h)
三、专题总结 ✨
递归解题模板
def recursion(node, params):
# 1. 边界条件（必须）
if node is None:
return base_value
# 2. 处理当前层（可选）
# ...
# 3. 递归左右子树
left_result = recursion(node.left, params)
right_result = recursion(node.right, params)
# 4. 合并结果（可选）
result = merge(left_result, right_result)
# 5. 返回
return result
递归要点速记
常见递归题型
统计类：二叉树的深度、节点数、左叶子之和
判定类：是否存在路径满足条件和
构建类：根据前序 / 中序遍历构建二叉树