难度: Medium
Submission
运行时间: 83 ms
内存: 24.1 MB
class Solution:
def findRoot(self, tree: List['Node']) -> 'Node':
if not tree:
return None
node_set = set(tree) # 创建一个集合来存储所有节点的引用
# 遍历树中的每个节点，并从集合中移除其子节点的引用
for node in tree:
for child in node.children:
if child in node_set: # 只有在集合中存在时才移除，避免重复移除
node_set.remove(child)
# 集合中剩下的那个节点就是根节点
return list(node_set)[0] if node_set else None
Explain
这个题解使用了集合来找出N叉树的根节点。首先，它将所有节点存储到一个集合中。接着，它遍历每一个节点，对于每个节点的所有子节点，从集合中移除这些子节点。因为所有非根节点都会作为某个节点的子节点出现，最后集合中剩下的唯一节点就是根节点，因为根节点不会被任何节点作为子节点引用。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findRoot(self, tree: List['Node']) -> 'Node':
if not tree:
return None
node_set = set(tree) # 创建一个集合来存储所有节点的引用
# 遍历树中的每个节点，并从集合中移除其子节点的引用
for node in tree:
for child in node.children:
if child in node_set: # 只有在集合中存在时才移除，避免重复移除
node_set.remove(child)
# 集合中剩下的那个节点就是根节点
return list(node_set)[0] if node_set else None
Explore
在题解中使用的集合是以节点对象的引用来存储的，这意味着即使某个节点在树的数据结构中被多次引用（例如，多个父节点引用同一个子节点），在集合中这个节点的引用只会存在一份。因此，当从集合中移除这个子节点时，不论它被多少个父节点引用，它都将从集合中完全移除，这不会影响根节点的识别，因为根节点从未作为任何节点的子节点。所以，这种方法可以正确处理节点中存在重复引用的情况。
如果`node_set`为空最直接的情况是输入的树列表`tree`本身就为空，即没有任何节点。在这种情况下，显然没有根节点可找，因此返回`None`是合理的。除此之外，在正常的N叉树结构中，`node_set`不应该在完成子节点移除后为空，除非输入数据结构本身是错误的（例如存在循环引用或不合法的节点结构）。因此，通常情况下`node_set`为空主要反映的是输入树列表`tree`为空的情况。
题解使用集合的主要优势在于其提供了高效的成员检查（时间复杂度为O(1)）和删除操作。使用列表实现相同的功能，虽然可能在空间上略有优势，但每次检查或删除元素的时间复杂度为O(n)，这会导致整体算法效率降低，尤其是在节点数量较多的情况下。而哈希表（字典）虽然也提供O(1)的时间复杂度进行成员检查和删除，但其内部机制与集合类似，并且在这种用例中，额外的键值对机制并不提供额外的好处。集合以其简洁和效率在此场景下是更合适的选择。
即使一个子节点被多个父节点引用，这种情况下算法依然能正确识别出根节点。在题解中，所有节点最初都加入到集合中，但每个节点无论被引用多少次，只要它至少是某个节点的子节点，它就会从集合中被移除。集合中不区分引用次数，只要一个节点作为子节点出现，它就会被移除。因此，最终在集合中剩余的节点，是从未作为任何其他节点的子节点的节点，即根节点。