背景：

因对公司底层代码进一步优化，对公共代码审核与优化。所以这次对树结构下手了！来让我们一起看看如何手撕这颗树。

源方法：

不多说了直接开撕代码

阅读代码

1. 首先，我斗胆带着大家读一读，看下我与大家的理解是不是一致的。

2. 在方法中，首先判断输入的集合是否为空，如果为空，则直接返回一个空集合。

3. 然后，通过循环遍历每一个节点，找到它的所有子节点，并将子节点添加到父节点的子节点集合中。为了避免父节点是它本身的情况，使用了一个selfIdEqSelfParent集合来记录所有满足这个条件的节点的id。

4. 最后，找出所有的根节点，即没有父节点的节点，并将它们添加到根节点集合中。

问题点

1. 在找到父节点的子节点时，使用了双重循环遍历的方式，导致时间复杂度较高。对于n个节点的树形结构，时间复杂度为O(n^2)。可以考虑使用更高效的算法来构建树形结构，例如使用哈希表来记录每个节点的id和对应的节点对象，然后通过一次循环就可以找到每个节点的父节点和子节点。

2. 自循环判断的逻辑存在问题。代码中使用了selfIdEqSelfParent集合来记录所有父节点是自己的节点的id。但是在循环遍历时，只记录了第一个满足条件的父节点的id，并没有在后续判断中对其他满足条件的节点进行处理。如果有多个节点的父节点都是自己，可能会导致构建出错误的树形结构。

3. 使用了通配符?来表示子节点的id的类型，但是没有使用实际的类型参数。这样可能导致在使用该方法时出现类型不匹配的问题。

优化后：

阅读代码

1. 首先，我们检查输入的树列表是否为空。如果为空，直接返回一个空的集合。

2. 然后，我们创建一个哈希表childrenMap，用于存储每个节点的子节点集合。对树列表中的每个节点进行遍历，我们获取该节点的父节点id。如果childrenMap中不存在该父节点id对应的子节点集合，我们创建一个新的空集合，并将该父节点id与其子节点集合放入childrenMap中。然后，将当前节点添加到其父节点的子节点集合中。

3. 接下来，我们再次遍历树列表中的每个节点。对于每个节点，我们检查它的id是否在childrenMap中存在对应的子节点集合。如果存在，我们将该子节点集合设置为当前节点的子节点集合。

4. 在构建完所有的子节点集合之后，我们开始找出根节点集合。我们创建一个空的根节点集合trees，以及一个id的集合allIds用于存储所有的节点id。首先，我们遍历树列表，将每个节点的id加入allIds中。然后，再次遍历树列表，检查每个节点的父节点id是否在allIds中存在。如果不存在，说明该节点是一个根节点，我们将其添加到根节点集合中。

5. 最后，我们返回得到的根节点集合。

6. 这样，我们就完成了树形结构的构建，并返回了根节点集合。

时间复杂度分析

1. 这段代码的时间复杂度是O(n)，其中n是树中节点的数量。

2. 首先，对于第一个for循环，我们将每个节点的父节点和它自身的映射存储在一个哈希表中。该循环遍历了树列表中的每个节点，所以时间复杂度是O(n)。

3. 然后，我们再次遍历树列表中的每个节点，检查是否存在与其id匹配的子节点集合。在每次迭代中，检查哈希表是否包含当前节点的id，并访问哈希表以获得子节点集合。这些操作的时间复杂度都是O(1)，因为哈希表的访问是常量时间复杂度。所以，该循环的时间复杂度也是O(n)。

4. 然后，我们找出根节点集合。我们首先遍历树列表，将所有节点的id存储在一个集合中。然后再次遍历树列表，检查每个节点的父节点id是否在集合中存在。这些操作的时间复杂度都是O(1)。所以这一部分的时间复杂度也是O(n)。

5. 综上所示，整个方法的时间复杂度是O(n)。

测试

本次采样数据共3423条。由之前417毫秒提升至4毫秒。

源代码：

优化后：