1. 问题背景与核心概念解析今天我们来拆解一道LeetCode上的树结构难题——2003. 每棵子树内缺失的最小基因值。这道题在周赛中出现时让不少选手感到棘手但其实只要掌握几个关键结论就能化繁为简。我们先明确题目要求给定一棵以节点0为根的树结构每个节点都有一个唯一的基因值即所有节点的基因值互不相同。需要为每个子树找出其内部缺失的最小正整数基因值。举个例子如果某子树包含的基因值为[2,3,5]那么缺失的最小正整数就是1如果包含[1,2,3]则缺失的最小值是4。关键提示题目中的缺失最小基因值实际上就是数学中的最小缺失正整数概念Mex, Minimum Excluded Value这与经典的数组找缺失最小正整数问题一脉相承。2. 三大核心结论及其证明2.1 结论一无1子树的处理策略现象观察当某子树中完全不包含基因值1时该子树的答案必定是1。这是所有正整数中最小的一个且题目保证基因值互不相同。逻辑证明根据Mex定义我们需要找的是不在集合中的最小正整数若集合中不存在1则1就是最小的缺失值这一结论与子树的具体结构无关是全局性结论实现技巧可以通过一次DFS预处理标记出哪些子树包含1对于不包含1的子树可以直接返回1无需进一步计算2.2 结论二含1子树的链式特性关键发现所有包含基因值1的子树它们的根节点实际上形成了一条从原始根节点节点0到基因值为1的节点的路径。这是因为子树包含1的条件是该节点在1的祖先路径上树结构中一个节点的子树包含另一个节点的条件是前者是后者的祖先因此只有1节点及其祖先节点的子树才会包含1实例说明 考虑如下树结构0 (val2) └── 1 (val1) └── 2 (val3)这里只有节点0和节点1的子树包含1它们正好形成0→1的路径。2.3 结论三链上节点的计算顺序最优策略对于包含1的那些子树即链上的节点我们应该从基因值为1的节点开始沿着祖先路径向上计算。这是因为子树的Mex值具有单调不减的性质越靠近叶子节点的子树包含的基因值越少Mex计算越简单可以利用已计算的子节点结果来优化父节点的计算算法选择使用哈希集合来维护当前路径上的基因值从1节点开始初始Mex设为2沿着父节点回溯动态更新Mex值3. 算法实现与优化细节3.1 预处理阶段建立树结构和定位1节点def build_tree(parents): tree defaultdict(list) one_pos -1 for i, p in enumerate(parents): tree[p].append(i) if vals[i] 1: one_pos i return tree, one_pos这个预处理步骤完成了两件事将父节点表示法转换为邻接表形式记录基因值1所在的节点位置3.2 标记包含1的子树def mark_contains_one(tree, one_pos): contains_one [False] * len(vals) stack [one_pos] while stack: node stack.pop() contains_one[node] True for child in tree[node]: stack.append(child) return contains_one使用DFS遍历从1节点开始的所有子树标记这些节点为包含1。3.3 主算法实现def smallestMissingValueSubtree(parents, vals): n len(parents) res [1] * n tree, one_pos build_tree(parents) if one_pos -1: # 没有基因值1的特殊情况 return res contains_one mark_contains_one(tree, one_pos) # 处理链上的节点 current_mex 2 visited set() node one_pos while node ! -1: # 收集当前节点的所有子节点基因值不包括已访问的 stack [node] while stack: curr stack.pop() if vals[curr] in visited: continue visited.add(vals[curr]) for child in tree[curr]: stack.append(child) # 更新Mex值 while current_mex in visited: current_mex 1 res[node] current_mex node parents[node] # 移动到父节点 return res4. 复杂度分析与边界情况4.1 时间复杂度建树和定位1节点O(N)标记包含1的子树O(N)主处理流程每个节点最多被访问一次Mex更新过程整体是O(N)因为Mex最多增加到N1总复杂度O(N)4.2 空间复杂度树结构的存储O(N)包含1的标记数组O(N)已访问基因值的集合最坏O(N)总空间O(N)4.3 边界情况处理没有基因值1的情况所有子树的Mex都是1直接返回全1数组基因值1在根节点只有根节点需要计算Mex其他节点可以直接返回1单节点树如果节点值为1Mex为2否则Mex为15. 实战技巧与常见错误5.1 调试技巧可视化小规模测试用例 手工绘制树结构标注每个节点的基因值手动计算预期结果。关键检查点确认1节点定位正确验证包含1的子树标记正确检查Mex更新逻辑是否准确5.2 常见错误错误假设基因值范围误认为基因值在1-N范围内实际上基因值可以是任意正整数Mex更新顺序错误应该先收集所有基因值再统一计算Mex而不是边收集边计算忽略父节点指针终止条件根节点的父节点通常是-1需要正确处理这个边界5.3 性能优化基因值离散化如果基因值范围很大但数量少可以先映射到连续区间但题目中N≤10^5通常不需要双指针Mex优化维护当前Mex候选值使用位图代替哈希集合当N很大时并行处理非链节点不包含1的子树可以并行处理但在编程竞赛中通常不需要6. 同类问题扩展掌握了这道题的解法后可以解决一系列类似问题子树Mex查询动态版本支持修改节点值需要更复杂的数据结构路径Mex问题计算树上路径的Mex可能需要树链剖分带权Mex问题每个值有权重求最小权重和Mex区间Mex问题数组区间查询离线处理线段树这道题很好地展示了如何将树结构的特性与算法设计相结合。通过分析问题本质得出的三个核心结论不仅适用于本题也为处理其他树结构问题提供了思路框架。在实际编码时注意处理好预处理和Mex更新的细节就能高效解决这个问题。