页面加载中…
一套递归框架，解决 90% 的二叉树题
二叉树是递归思维的最佳训练场，几乎所有树题都能用「递归三问：返回值/参数/单层逻辑」拆解。本路径从前中后序与层序四大遍历框架出发，逐步打通属性计算、树的构造、BST 专项，最终迎战 LCA 与序列化等综合压轴题。19 道题覆盖 Hot 100 中全部高频树题，吃透后面试树题无盲区。
适合：想把树的遍历与递归框架吃透的人
递归三问建框架：①函数返回什么，②需要哪些参数，③单层如何处理左右子树。前/中/后序递归 + 层序 BFS 队列是所有树题的底层模板，先把四种遍历框架背进肌肉记忆。
开局热身：swap 左右子树，直接套递归三问——返回翻转后的根、参数是当前节点、单层逻辑交换左右。本题是整个路径的递归模板起点。
翻转只需前序，中序要先左后根后右，必须同时掌握递归写法和用栈模拟的迭代写法——后续 BST 题全靠中序有序性。
前两题是纵向 DFS，层序换横向 BFS：队列 + while 外层 + for 内层记当层 size，这个双层循环是所有层序变体的母版。
复用上一题层序 BFS 母版，只取每层最后一个节点加入结果；也可用后序 DFS 记录每层首次访问节点。同框架两种用法。
属性题核心手法是「后序回传信息」：子树算完再告诉父节点结果。掌握「后序 + 全局变量」组合拳后，高度、直径、路径和等题型全部统一到同一个递归骨架。
后序回传的最简形式：递归返回左右子树深度，取 max+1 传回父节点。「return max(left,right)+1」是所有属性题的最小原型。
最大深度比较同侧，对称比较镜像——把单树递归改成双指针同步递归，参数从一个节点变成两个节点（左外 vs 右外、左内 vs 右内）。
对称返回布尔，平衡需同时拿高度；在后序返高度的基础上用 -1 作哨兵标记「已不平衡」向上传递，避免重复计算——带哨兵的后序回传。
平衡树后序回传高度，直径同样回传高度；但最大值可能不过根，须用全局变量在后序回溯时用左高+右高更新——「后序回传+全局更新」与平衡树的关键区别。
直径用后序拿高度，路径和改用前序携带余量向下传：每层减去当前值，到叶子余量为零即成。后序回传换成前序传参，两个方向都要掌握。
最大深度取 max，最小深度看似只改 min，陷阱在单侧为空时不是叶子，必须只对非空子树取 min，专练边界条件判断。
构造题要熟悉「前序定根 + 中序划分左右」的切割逻辑；BST 题则把「中序遍历有序」这一性质转化为解题切入点。两类题各有固定套路，掌握后立刻形成模板。
前序首元素是根，在中序中定位后左侧是左子树、右侧是右子树，递归切割；哈希表存中序下标，把暴力 O(n²) 优化到 O(n)。
构造题从数组建树，此题反向将树压扁为前序链表：后序先压扁左右子树，再把左子树接到右侧、原右子树接到末尾，后序合并与构造树对称。
BST 中序遍历严格递增，验证 BST 等价于验证中序序列单调递增——套里程碑 1 的中序框架，用前驱变量记上一个节点值比较即可。
验证 BST 利用中序单调，BST 的 LCA 同样利用值大小：p、q 都小则往左，都大则往右，一大一小则当前节点即 LCA，比普通 LCA 简单。
BST-LCA 只需比大小，累加树要从大到小累加，即反向中序（右→根→左），边遍历边用累加变量更新节点值——中序框架倒着写即可。
压轴四题各引入一个「跨层信息流动」技巧：LCA 的后序汇聚、最大路径和的跨根合并、路径总和 III 的前缀和、序列化的先序重建。每题单独成一类范式，是树题天花板。
普通树无值大小可用；改为后序分别从左右子树找 p 和 q，谁先在两侧各找到一个谁就是 LCA——「后序汇聚两侧信息」的典型范式。
LCA 后序汇聚两侧节点；此题路径不限起止，改用前缀和哈希表：DFS 时查「当前前缀和 - 目标值」得路径数，O(n²) 降到 O(n)。
前缀和哈希表统计路径数量；最大路径和改为后序回传单侧最大贡献，跨根值=左+根+右，负贡献剪掉（与 0 取 max），全局变量记最大。
前序遍历时把空节点记为「#」，反序列化按相同前序顺序递归消费列表还原树——复用里程碑 3「前序定根」思路，无需中序辅助，一遍扫描完成。