EverydayTopics-2023-Oct-31

题目

2003. 每棵子树内缺失的最小基因值

解法

本来我自己想的思路是：

1. 对于每个节点计算其子树
2. 对于每个分离下来的子树计算其缺失的最小基因
3. 记录最小基因

但是这么来算的话，每次都要对子树进行一次遍历，时间复杂度大概有O(n)了，估计按照我模拟的思路也是太久了，于是遂作罢，直接看答案了。

官方题解有两个：

1. dfs+启发式合并
   但启发式合并我看不懂，后面看了一下OiWIKI也是非常一知半解，就没有耗费更多的时间在上面，直接看dfs了。

2. 纯dfs
   dfs的解法是：

   1. 若树中无基因值为1的节点，则1为任意子树的最小缺失基因值。
   2. 若树中含有基因值为1的节点，则对于其的任意子树有以下两种情况：
      1. 以该节点为根的子树不包含基因值为1的节点
         那么其缺失值就为1
      2. 以该节点为根的子树包含基因值为1的节点
         在情况2中，该节点肯定为基因值为1的节点的先祖节点，即在基因值为1的节点的上面。

   同时我们又知：父节点的基因值集合肯定是大于子节点的基因值集合的。

写到这里发现上面这一句有啥用呢？也推不出来什么结果。这题的思路还是不是很清晰，明天如果有空的话再理一下吧。

知识：

1. dfs
2. 树状结构
3. 启发式合并（不会）