这份笔记涵盖了从 Day 9 (递归思维建立) 到 Day 10 (迭代与算法融合) 的完整知识体系。内容设计为适合 VitePress/Obsidian 等 Wiki 系统的 Markdown 格式。
🌳 二叉树 (Binary Tree)：从递归到算法融合
归档日期: 2026/01/20
涵盖周期: Day 9 - Day 10
核心主题: 递归思维、系统栈与堆迭代、自底向上模式、前缀和回溯
1. 核心思维转换 (Mental Model)
二叉树是数据结构的分水岭，核心在于思维从“线性”向“分叉”的跨越，以及对内存栈帧（Stack Frame）的深刻理解。
1.1 递归的本质：钻井与铺路
递归不是魔法，而是 Pointer Chasing（指针追逐） 与 System Stack（系统栈） 的结合。
钻井 (Drill Down)：函数调用自身，压栈。对应 前序遍历 (Pre-order) 的逻辑（先办事，再深入）。
铺路 (Pave Up)：函数
return，弹栈。对应 后序遍历 (Post-order) 的逻辑（先深入，回来时办事）。
🚨 内存警示：栈溢出 (Stack Overflow)
通过 infiniteRecursion 实验测得，本机（及大多数标准 OS 环境）的 Stack Limit 约为 8MB。
在不做尾递归优化的情况下，最大递归深度约为 74,000 层。
启示：生产环境或处理退化为链表的树时，慎用递归，优先考虑迭代法或增大栈空间。
:::
1.2 树的物理存储
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 内存模型：Heap 中分散的节点通过 Pointer 相互连接2. 遍历体系 (Traversals)
2.1 DFS：递归全家桶
利用系统栈隐式维护路径。
前序 (Pre):
根 -> 左 -> 右(DFS 序)中序 (In):
左 -> 根 -> 右(BST 排序)后序 (Post):
左 -> 右 -> 根(删除节点、算高度)
2.2 BFS：层序遍历
利用 Queue (FIFO) 进行横向扫描。
核心模版 (分层处理)：
while (!q.empty()) {
int size = q.size(); // 🔒 锁定当前层节点数
for (int i = 0; i < size; i++) { // 只处理这一层的
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}TIP
工业级接口写法 避免在递归函数中直接返回 vector（会导致大量内存拷贝）。应采用 Helper Function 模式：void traversal(node, vector<int>& res) 通过引用传递结果集。
2.3 迭代法 (Iterative DFS)
利用 std::stack 在堆内存中模拟递归，避免栈溢出。中序迭代 是难点。
逻辑状态机：
Drill Left: 只要有路，拼命往左钻，沿途入栈。
Backtrack: 没路了，弹出栈顶（访问），转向右子树。
代码段
关键代码 (中序)：
while(root != nullptr || !st.empty()) {
if(root != nullptr) {
st.push(root); // 存包
root = root->left; // 钻井
} else {
root = st.top(); // 取包
st.pop();
res.push_back(root->val); // 办事
root = root->right; // 转向
}
}3. 自底向上模式 (Bottom-Up Pattern)
解决树高、平衡、直径等问题的通用解法。核心在于 后序遍历：先拿到子树的信息，整合后再汇报给父节点。
3.1 模式解析
输入：子树的返回值（高度、是否平衡等）。
处理：当前节点的逻辑（计算直径、判断差值）。
输出：向父节点汇报自身属性（通常是
max(L, R) + 1）。
3.2 经典案例：二叉树直径 ([543])
利用 全局变量 记录过程中的最大值，利用 返回值 维护递归逻辑。
优化技巧 ([110] 平衡二叉树)
如果发现子树已经不平衡，直接返回特定错误码（如 -1），实现 剪枝，将复杂度从 降为 。
4. 算法融合：前缀和与回溯
题目：[437] 路径总和 III (Path Sum III)
难点：寻找任意向下的路径和等于 target。
技术栈：DFS + Hash Map (Prefix Sum) + Backtracking。
4.1 数学原理
4.2 回溯的核心：时空隔离
Map 中永远只保存 当前节点到根节点 这一条路径上的前缀和。
进入节点：
map[currSum]++(注册)离开节点：
map[currSum]--(注销)
4.3 代码易错点
// ❌ 错误写法
if (prefixMap.count(target - currSum))
// ✅ 正确写法：历史 = 当前 - 目标
if (prefixMap.count(currSum - target))5. 待办与复习 (To-Do)
待办: [215] 数组第 K 大元素的 Quick Select 解法（Day 11/12 安排）。
待办: 《Effective C++》条款 11-12 (operator= 实现细节)。
复习: 每天手写一次 DFS 递归模版与中序迭代模版，保持肌肉记忆。