预计阅读时间：9 分钟
二叉树
树题是刷题修行的主线任务之一。本合集按套路分节收录二叉树题目：每题给出关键观察、做法与复杂度。
二叉搜索树
BST 的第一反应是中序遍历——中序遍历 BST 会得到一个严格递增的序列，大量题目围绕这条性质展开。
leetcode 2476
中序遍历得到递增序列，对每个询问在序列上做一次二分查找。时间复杂度 $O(n \log n)$。
leetcode 1932
合并 BST。需要先观察出两条性质：
- 根节点是唯一的。 能成为最终根的树，其根值没有出现在任何叶子上，也就无法「被」合并；如果这样的树不止一棵，最后不可能合并成一棵树。
- 合并方式是唯一的。 若一棵树能被多个叶子合并，假设最后仍能合成一棵树，树中必然出现值相同的节点，违反 BST 性质。
由这两条性质得到做法：
- 先找根：根值没有出现在任何叶子上的那棵树，有且只有一个。
- 从根开始中序遍历：非叶节点正常走；走到叶节点时，把值匹配的树接过来（用哈希表按根值找树，$O(1)$），接完继续中序。全程校验中序结果严格递增，以保证合并后仍是 BST。
时间、空间复杂度 $O(n)$。
leetcode 1373
BST 一般配中序，但这题不行：要找的必须是一棵完整子树，中序遍历只能截出「残缺」的子树片段。判 BST 的同时还必须知道这棵子树的节点和，自然想到自底向上：后序遍历判 BST，同时向上多传一个子树和。这套自底向上的写法不熟的话，可以先拿 leetcode 98 练手。
创建二叉树
leetcode 1382
BST 转平衡 BST：中序遍历得到递增序列，每次取中点作根递归建树。
leetcode 536
字符串解析 + 递归建树。算法本身显然，处理上需要技巧：如果每次都去解析子串、切分左右子树再构建，容易写成 $O(n^2)$。正确姿势是用全局 index 扫一遍字符串，边扫边贪心建树——题目保证总是先建左节点；建完左节点还能看到左括号，说明接下来是右节点；递归返回后全局 index 加一跳过右括号。
最近公共祖先
leetcode 236
普通二叉树 LCA，用分类讨论的方式思考递归返回值：
- 遍历到空节点：返回该节点本身（root）。
- 遍历到 p 或 q：不必继续向下。另一个点要么在它子树里，要么在它祖先的另一侧，两种情况都返回节点本身（root）。
- p、q 分居左右子树：返回当前节点（root）。
- p、q 都在左子树：返回左子树递归结果（root.left 方向）。
- p、q 都在右子树：返回右子树递归结果（root.right 方向）。
- 左右子树都没找到：返回空。
需要遍历整棵树，时间复杂度 $O(n)$。
leetcode 235
BST 上的 LCA。按普通二叉树的方式做当然可以，$O(n)$；但利用 BST 性质（左子树全小于当前节点、右子树全大于当前节点），不需要递归整棵子树，按节点值分类讨论即可：
- 题目保证 p、q 存在，所以不会走到空节点。
- 遍历到 p 或 q：不必继续，另一个点一定在它的子树中（「在祖先另一侧」的情况被 BST 性质排除），返回节点本身。
- p、q 分居左右（用值判断）：返回当前节点。
- p、q 都在左子树（用值判断）：递归左子树。
- p、q 都在右子树（用值判断）：递归右子树。
只沿一条路径下行，时间复杂度 $O(h)$，h 为树高。注意 BST 可能退化成链表，此时 $h = n$，最坏仍是 $O(n)$。
leetcode 1676
求 k 个节点的 LCA。若两两求再合并，复杂度 $O(kn)$。把节点数组转成集合，每次递归 $O(1)$ 判断当前节点是否在集合内，在集合内就返回当前节点——其余分析和写法与两点版完全一致。
二叉树 BFS
leetcode 2471
按层遍历本身是模板，重点在每层求最小交换次数。先离散化，然后从头扫：对每个位置，若数不在自己正确的位置上，就顺着「它正确的位置上现在是什么数」一路追下去，最终会追出一个环（置换环）；每个环的最小交换次数是环大小减一。找环 $O(n)$，离散化需要排序 $O(n \log n)$，整体 $O(n \log n)$。
二叉树直径
leetcode 543
定义题。经过某个节点的最长路径 = 左子树最长链 + 右子树最长链 + 2，所以在递归求每个节点向下最长链的同时顺手更新直径即可。注意最长路径不一定经过根节点。
leetcode 687
把 dfs 定义为：以当前节点为起点、向下延伸的最长同值路径长度。左右子树都无条件递归，约束加在计算返回值时——判断当前节点与左右孩子值是否相等，相等则链长加一，并用「左链 + 右链」更新全局答案。一遍遍历 $O(n)$ 解决。注意返回值只能取左右链的较大者：向上返回时只能选一条路径。
树上路径状态压缩
leetcode 1457
关键观察：路径能重排成回文，等价于至多一个数字出现奇数次（回文两两配对，落单的至多一个放中间）。所以 dfs 遍历时统计路径上各数字出现次数的奇偶即可。
最初用「每个节点带一个字典统计次数」的朴素写法过了，但效率很低——每个子节点都要拷贝一份字典。注意到数字只有 1 到 9 共九种，直接状态压缩：把奇偶性压进一个整数，按位异或维护，到叶子处判断二进制中至多一个 1。
数 1 可以暴力（九位是常数），但这里有个技巧：x & (x - 1) 会消掉最低位的 1，结果非 0 说明至少还有第二个 1，直接判负。
时间复杂度 $O(n)$，空间复杂度 $O(h)$（递归栈），h 为树高。
class Solution:
def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
def dfs(root, mask):
if root is None:
return 0
mask ^= (1 << (root.val - 1))
if root.left is None and root.right is None:
return 1 if mask & (mask - 1) == 0 else 0
return dfs(root.left, mask) + dfs(root.right, mask)
return dfs(root, 0)
同型题 leetcode 1371：求元音全部出现偶数次的最长子串，同样是奇偶位掩码，配合前缀异或使用。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。