二叉树

副标题 / 摘要 层序遍历是二叉树 BFS 模板的起点。真正关键的不是“用队列”，而是“如何把同一层的节点切分出来”。本文按 ACERS 结构拆解 LeetCode 102 的按层处理方法、DFS 深度分桶备选方案，以及工程里常见的分层遍历场景。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、BFS、DFS、队列、层序遍历 SEO 关键词：Hot100, Binary Tree Level Order Traversal, 二叉树的层序遍历, BFS, 队列, LeetCode 102 元描述：系统讲透 LeetCode 102 的层序 BFS、层宽控制与 DFS 深度分桶思路，并延伸到组织树、菜单树和波次执行等工程场景。 目标读者 想把 BFS 模板真正固定下来的 Hot100 刷题读者 会普通遍历，但一到“按层输出”就容易把层边界写乱的开发者 需要按深度分组展示树形结构的工程师 背景 / 动机 LeetCode 102 是树题里最标准的 BFS 入门题之一。 它训练的不是“遍历所有节点”，而是两件更重要的事： 如何用队列维护“下一批待处理节点” 如何准确切出“这一层”和“下一层”的边界 很多 BFS bug 都来自这里： 在遍历当前层时直接用不断变化的 queue.length 一边弹当前层，一边把新孩子混进当前层结果 忘记空树处理，导致访问空指针 把 102 的模板写稳，后面的： 右视图 每层平均值 锯齿层序遍历 最小深度 / 最大深度的 BFS 写法 都会自然很多。 ...

副标题 / 摘要 对称二叉树的难点不在遍历，而在“比较方向”。你比较的不是左对左、右对右，而是镜像位置上的节点对。本文按 ACERS 结构拆解 LeetCode 101 的镜像递归合同、BFS 成对入队写法，以及工程中的对称结构校验场景。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、DFS、BFS、对称性 SEO 关键词：Hot100, Symmetric Tree, 对称二叉树, 镜像递归, BFS, LeetCode 101 元描述：系统讲透 LeetCode 101 的镜像递归与 BFS 对称校验思路，并延伸到布局树与拓扑模板的对称检查。 目标读者 刚从 100 相同的树过渡到“镜像比较”的刷题读者 会写普通树递归，但对“外侧 / 内侧”比较关系容易写乱的开发者 需要在布局树、模板树、镜像结构里做左右对称校验的工程师 背景 / 动机 LeetCode 101 很适合作为树题里的“方向感”训练： 你要先意识到，对称不是“左右子树完全一样” 它要求的是“左边看过去”和“右边镜像过来”之后一致 也就是说，比较方向从“同向”变成了“交叉” 很多人做这题时容易犯三类错误： 还沿用 100 的思路，写成 left.left 对 right.left 只比较节点值，不比较空节点位置 先翻转一棵子树再比较，结果多做了一轮变换，逻辑也更绕 这题真正训练的是“镜像递归模板”。掌握后，树对称、树镜像、结构匹配等题都会更清楚。 核心概念 镜像关系：左子树的左边，要和右子树的右边对应；左子树的右边，要和右子树的左边对应 外侧 / 内侧配对：left.left 对 right.right，left.right 对 right.left 成对递归：递归函数参数是两个节点，表示“这两个位置是否互为镜像” 成对入队：BFS 里队列保存的不是单个节点，而是需要一起比较的节点对 A — Algorithm（题目与算法） 题目还原 给你一个二叉树的根节点 root，检查它是否轴对称。 ...

副标题 / 摘要 翻转二叉树是一道看起来非常短、却能快速检验你是否真正理解递归结构的题。本文围绕 LeetCode 226 拆解“交换左右子树”的本质，给出递归 / BFS 两种做法，以及结构镜像在工程中的迁移思路。 预计阅读时长：8~10 分钟 标签：Hot100、二叉树、递归、BFS、树变换 SEO 关键词：Hot100, Invert Binary Tree, 翻转二叉树, 树镜像, 递归, LeetCode 226 元描述：讲清 LeetCode 226 的递归与 BFS 解法，并延伸到布局镜像、结构变换等工程场景。 目标读者 想检验自己是否真正理解“递归作用在整棵树每个节点上”的刷题读者 看到树题就下意识写遍历，但不确定该在什么时机处理当前节点的开发者 需要做树形结构镜像、布局翻转或对称转换的工程师 背景 / 动机 226 的代码通常很短，但它的思维非常典型： 当前节点要做什么？ 把 left 和 right 交换。 子问题是什么？ 左右子树本身也都要继续翻转。 这就是非常纯粹的“当前操作 + 递归处理子问题”。 如果你对这题没有完全吃透，往往会出现： 只交换根节点，不继续处理子树 交换后递归方向写乱 把本来能原地完成的事，额外重建一棵新树 核心概念 树镜像（mirror）：把每个节点的左子树与右子树对调 原地变换（in-place transform）：不新建整棵树，只交换指针 递归分治：当前节点处理完后，左右子树仍是同类型问题 BFS 层序变换：也可以按层把每个节点的左右孩子交换 A — Algorithm（题目与算法） 题目还原 给你一棵二叉树的根节点 root，请将这棵树翻转，并返回翻转后的根节点。 输入输出 名称 类型 描述 root TreeNode 二叉树根节点，可以为空 返回值 TreeNode 翻转后的根节点 示例 1 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 解释: 原树左右子树整体对调后，所有节点都完成镜像翻转。 示例 2 输入: root = [2,1,3] 输出: [2,3,1] 示例 3 输入: root = [] 输出: [] 约束 树中节点数目在 [0, 100] 内 -100 <= Node.val <= 100 C — Concepts（核心思想） 思路推导：为什么“交换 + 递归”就够了 假设当前节点是 node，我们要做的事情只有两步： ...

副标题 / 摘要 “最大深度”是树递归最标准的起手式。你只要真正理解“当前树的答案依赖左右子树答案”的定义，整类树形 DP / DFS 题都会顺很多。本文以 LeetCode 104 为核心，系统讲解递归 DFS、层序 BFS 与工程迁移方法。 预计阅读时长：9~11 分钟 标签：Hot100、二叉树、DFS、BFS、递归 SEO 关键词：Hot100, Maximum Depth of Binary Tree, 二叉树的最大深度, DFS, BFS, LeetCode 104 元描述：从深度定义出发，讲清 LeetCode 104 的 DFS 和 BFS 解法，并附多语言可运行代码。 目标读者 刚开始刷树题，想把“树递归返回值”真正吃透的同学 能写遍历，但一遇到“求高度 / 求路径 / 求答案”就容易混乱的开发者 需要在菜单树、组织架构、嵌套 JSON 等层级数据里做深度分析的工程师 背景 / 动机 LeetCode 104 看起来像一道“送分题”，但它几乎是所有树递归的母题： 你需要先回答“空树深度是多少” 再回答“当前节点的答案依赖谁” 最后把关系写成 1 + max(left, right) 一旦这个递归定义真正建立起来，后续的平衡二叉树、直径、路径和、最近公共祖先都会更容易进入状态。 核心概念 深度 / 高度：这里按题意，根到最远叶子节点的节点数 后序式思维：想知道当前节点答案，必须先知道左右子树答案 DFS：递归向下，回溯时组合答案 BFS：按层遍历，最后一层编号就是树深度 A — Algorithm（题目与算法） 题目还原 给定二叉树根节点 root，返回其 最大深度。 ...

副标题 / 摘要 二叉树遍历是树题模板的起点，中序遍历则是“递归思维”和“显式栈模拟”最典型的一题。本文按 ACERS 结构拆解 LeetCode 94，把左-根-右的访问顺序、迭代栈写法和工程迁移价值一次讲清。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、DFS、栈、中序遍历 SEO 关键词：Hot100, Binary Tree Inorder Traversal, 二叉树的中序遍历, 中序遍历, 显式栈, LeetCode 94 元描述：从递归到显式栈，系统讲透 LeetCode 94 二叉树中序遍历，并给出工程场景迁移与多语言实现。 目标读者 正在刷 Hot100，希望把树遍历模板固定下来的同学 刚从数组 / 链表过渡到树结构，容易把前序、中序、后序顺序写混的开发者 需要在 BST、表达式树、抽象语法树里复用“左-根-右”思想的工程师 背景 / 动机 中序遍历本身不复杂，但它的训练价值很高： 它是“递归 = 隐式栈，迭代 = 显式栈”最容易建立直觉的一题 它能帮助你稳定掌握“先一路向左，再回退访问根，再转向右子树”的过程 在 二叉搜索树（BST） 里，中序遍历天然得到有序序列，工程迁移价值很强 很多人第一次写树题不是逻辑不会，而是： 不清楚访问顺序到底是谁先谁后 迭代版不知道什么时候入栈、什么时候出栈 一旦树为空或只有单边链，代码就容易写乱 这题把模板练熟，后面的验证 BST、找第 k 小元素、恢复二叉搜索树等题会更顺。 核心概念 中序遍历：按照 左子树 -> 根节点 -> 右子树 的顺序访问 DFS（深度优先搜索）：树遍历最常见的组织方式，中序遍历就是 DFS 的一种访问顺序 显式栈：把递归调用栈手动写出来，用栈保存“回头还要处理的节点” 树高 h：空间复杂度通常写成 O(h)，平衡树约为 O(log n)，极端退化链表时是 O(n) A — Algorithm（题目与算法） 题目还原 给定二叉树根节点 root，返回它的 中序遍历 结果。 ...

副标题 / 摘要 “路径不必从根开始、但必须向下”使得这题无法用简单的根到叶 DP 解决。本文用 ACERS 结构讲透 树上前缀和：把任意向下路径转化为“两个前缀和的差”，用哈希表在线计数，做到 O(n) 一次 DFS 统计所有答案。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、前缀和、DFS、哈希表 SEO 关键词：Path Sum III, 路径和 III, 树上前缀和, 前缀和哈希, LeetCode 437, Hot100 元描述：前缀和 + 哈希表在线统计二叉树向下路径和等于 targetSum 的条数，包含推导、复杂度对比与多语言实现。 目标读者 刷 LeetCode、希望把“树 + 哈希”题型沉淀成模板的学习者 对“路径不从根开始”的树题容易写成 O(n^2) 的同学 做日志调用链 / 层级数据分析，需要在树结构上做区间统计的工程师 背景 / 动机 很多“树上的路径问题”都有一个坑： 你以为要从根出发、或要到叶子结束，但题目允许 从任意节点开始、到任意节点结束（但方向必须向下）。 这意味着： 你不能只维护“从根到当前”的一种状态就完事； 也不能枚举所有起点（那会退化成 O(n^2)）； 更不能用滑动窗口（节点值可正可负，窗口单调性不存在）。 这题最值得掌握的点是：把“树上任意向下路径”化为“同一路径上的两个前缀和之差”。 一旦你掌握了这个模型，很多树上统计题都会变成“前缀和 + 哈希表”的熟悉配方。 核心概念 向下路径：只能从父到子（不能回头、不能跨分支） 前缀和（prefix sum）：从根到当前节点路径上所有节点值的累加 差分计数：若 curSum - prevSum = target，则 prevSum = curSum - target 路径内哈希表：只统计“当前 DFS 路径上的前缀和”，回溯时必须撤销（否则会把不同分支混在一起） A — Algorithm（题目与算法） 题目还原 给定一个二叉树的根节点 root 和整数 targetSum，求二叉树里 节点值之和等于 targetSum 的向下路径 的数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须向下（只能从父节点到子节点）。 ...