LeetCode Find Root of N-Ary Tree 深度解析：从乱序节点列表定位根节点的两种解法（基于 Leetcode solutions 仓库）

LeetCode Find Root of N-Ary Tree 深度解析：从乱序节点列表定位根节点的两种解法（基于 Leetcode solutions 仓库）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 articles/find-root-of-n-ary-tree.md 为主体，系统讲解「给定一棵 N 叉树的所有节点（乱序），找出根节点」这一经典树问题的完整求解思路。你将掌握基于哈希集合的 O(N) 空间解法与基于「父加子减」求和的 O(1) 空间解法，理解两者背后的数学原理、多语言实现差异与边界陷阱，从而在面试与刷题中快速、准确地复现该题解。本文代码与讲解来自当前仓库的多语言解题集合，与仓库中 Python、Java、JavaScript、C++、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart 等 14 种语言的题解风格保持一致（参见 README.md）。

问题背景与前置知识

该问题属于N 叉树（N-ary Tree）系列题目：输入是一个顺序任意的节点列表tree，其中包含整棵树的全部节点引用，但既没有给出层序（level-order），也没有任何遍历顺序的保证，更不保证根节点排在列表首位。我们需要做的是：仅凭这个列表，找出哪一个节点才是整棵树的根。

动手之前，需要具备以下基础：

• N-ary Tree 结构：节点可以有任意多个子节点，通常以val（节点值）和children（子节点列表）两个字段表示；
• Hash Set / Hash Map：利用集合的 O(1) 平均查找复杂度来记录"已见过的值"，从而快速判断某个节点是否曾经作为子节点出现；
• 树的基本性质：在一棵有向的树中，除根节点外的每一个节点都恰好是某一个节点的子节点；而根节点从来不会出现在任何节点的 children 列表中。这正是整个问题的解题钥匙。

核心洞察：根节点是唯一"从不出现在别人孩子列表里"的节点

无论输入列表如何乱序，以下事实恒成立：

• 每个非根节点都恰好作为某个父节点的 child 出现一次；
• 根节点作为父节点存在，但永远不会作为任何节点的 child 出现。

因此，找出"从未当过孩子"的节点，就找到了根。围绕这一洞察，可以设计出空间复杂度不同的两种算法。

解法一：哈希集合法（O(N) 时间，O(N) 空间）

直觉

利用集合收集"所有被当作孩子的节点值"。遍历两遍列表：

1. 第一遍：把每个节点的所有子节点值加入seen集合；
2. 第二遍：扫描所有节点，第一个值不在seen中的节点就是根节点。

因为根节点永远不会被加入seen，而其他节点都会被加入，所以该节点必然唯一。

算法步骤

1. 创建一个空集合seen，用于存放所有子节点的值；
2. 遍历tree中的每个节点，将其children列表中所有子节点的值加入seen；
3. 再次遍历tree，找出值不在seen中的节点；
4. 返回该节点，即为根节点。

多语言实现

以下实现保留了原文档中的核心写法（seen既可以存节点值，也可以存节点引用，只要前后一致即可）：

class Solution: def findRoot(self, tree: List['Node']) -> 'Node': # set that contains all the child nodes. seen = set() # add all the child nodes into the set for node in tree: for child in node.children: # we could either add the value or the node itself. seen.add(child.val) # find the node that is not in the child node set. for node in tree: if node.val not in seen: return node

class Solution { public Node findRoot(List<Node> tree) { // set that contains all the child nodes. HashSet<Integer> seen = new HashSet<Integer>(); // add all the child nodes into the set for (Node node : tree) { for (Node child : node.children) // we could either add the value or the node itself. seen.add(child.val); } Node root = null; // find the node that is not in the child node set. for (Node node : tree) { if (!seen.contains(node.val)) { root = node; break; } } return root; } }

class Solution { public: Node* findRoot(vector<Node*> tree) { // set that contains all the child nodes. unordered_set<int> seen; // add all the child nodes into the set for (Node* node : tree) { for (Node* child : node->children) { // we could either add the value or the node itself. seen.insert(child->val); } } Node* root = nullptr; // find the node that is not in the child node set. for (Node* node : tree) { if (seen.find(node->val) == seen.end()) { root = node; break; } } return root; } };

class Solution { /** * @param {_Node[]} tree * @return {_Node} */ findRoot(tree) { // set that contains all the child nodes. const seen = new Set(); // add all the child nodes into the set for (const node of tree) { for (const child of node.children) { // we could either add the value or the node itself. seen.add(child.val); } } let root = null; // find the node that is not in the child node set. for (const node of tree) { if (!seen.has(node.val)) { root = node; break; } } return root; } }

public class Solution { public Node FindRoot(List<Node> tree) { // set that contains all the child nodes. HashSet<int> seen = new HashSet<int>(); // add all the child nodes into the set foreach (Node node in tree) { foreach (Node child in node.children) { // we could either add the value or the node itself. seen.Add(child.val); } } Node root = null; // find the node that is not in the child node set. foreach (Node node in tree) { if (!seen.Contains(node.val)) { root = node; break; } } return root; } }

func findRoot(tree []*Node) *Node { // set that contains all the child nodes. seen := make(map[int]bool) // add all the child nodes into the set for _, node := range tree { for _, child := range node.Children { // we could either add the value or the node itself. seen[child.Val] = true } } // find the node that is not in the child node set. for _, node := range tree { if !seen[node.Val] { return node } } return nil }

class Solution { fun findRoot(tree: List<Node>): Node? { // set that contains all the child nodes. val seen = HashSet<Int>() // add all the child nodes into the set for (node in tree) { for (child in node.children) { // we could either add the value or the node itself. seen.add(child.`val`) } } // find the node that is not in the child node set. for (node in tree) { if (node.`val` !in seen) { return node } } return null } }

class Solution { func findRoot(_ tree: [Node]) -> Node? { // set that contains all the child nodes. var seen = Set<Int>() // add all the child nodes into the set for node in tree { for child in node.children { // we could either add the value or the node itself. seen.insert(child.val) } } // find the node that is not in the child node set. for node in tree { if !seen.contains(node.val) { return node } } return nil } }

impl Solution { pub fn find_root(tree: Vec<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> { let mut seen = HashSet::new(); for node in &tree { for child in &node.borrow().children { seen.insert(child.borrow().val); } } for node in &tree { if !seen.contains(&node.borrow().val) { return Some(node.clone()); } } None } }

复杂度分析

• 时间复杂度：O(N)。两次线性扫描，每次对集合的插入与查询均为 O(1)（平均）；
• 空间复杂度：O(N)。seen集合最多保存 N-1 个子节点值；

其中 N 为输入列表的长度，即 N 叉树的节点总数。

实现要点解读

• Python 的set、Java/C# 的HashSet、C++ 的unordered_set、JavaScript 的Set、Go 的map[int]bool、Rust 的HashSet都提供平均 O(1) 的插入与查找，这是算法成立的数据结构前提；
• Rust 实现使用Rc<RefCell<Node>>共享所有权与内部可变性，遍历子节点时通过borrow()取引用；返回根节点时用clone()复制Rc指针而非深拷贝节点本身；
• Go 语言中map[int]bool取值后直接判断布尔值即可，省略了contains方法调用。

解法二：求和抵消法（O(N) 时间，O(1) 空间）

直觉

这是本题最具巧思的解法。回顾树的性质：

• 除根节点外，每个节点恰好出现一次"作为父节点"、一次"作为子节点"；
• 根节点只作为父节点出现，从不作为子节点出现。

于是可以这样"记账"：遍历每个节点时，把节点自身的值加上（当作父节点 +1），把它的每个子节点的值减去（当作子节点 -1）。经过整棵树后：

• 所有非根节点被加了一次、又减了一次，相互抵消，净贡献为 0；
• 根节点只被加了一次、从未被减，净贡献为它自身的值。

因此最终得到的valueSum恰好等于根节点的值。再扫描一遍列表，找到值等于valueSum的节点即可。该解法完全不需要哈希表，空间复杂度降为 O(1)。

算法步骤

1. 初始化valueSum = 0；
2. 遍历tree中的每个节点：
   • 将节点自身的值加到valueSum（把它当作父节点记账）；
   • 将该节点每个子节点的值从valueSum中减去（把它们当作子节点记账）；
3. 再次遍历tree，找到值等于valueSum的节点并返回。

多语言实现

class Solution: def findRoot(self, tree: List['Node']) -> 'Node': value_sum = 0 for node in tree: # the value is added as a parent node value_sum += node.val for child in node.children: # the value is deducted as a child node. value_sum -= child.val # the value of the root node is `value_sum` for node in tree: if node.val == value_sum: return node

class Solution { public Node findRoot(List<Node> tree) { Integer valueSum = 0; for (Node node : tree) { // the value is added as a parent node valueSum += node.val; for (Node child : node.children) // the value is deducted as a child node. valueSum -= child.val; } Node root = null; // the value of the root node is `valueSum` for (Node node : tree) { if (node.val == valueSum) { root = node; break; } } return root; } }

class Solution { public: Node* findRoot(vector<Node*> tree) { int value_sum = 0; for (Node* node : tree) { // the value is added as a parent node value_sum += node->val; for (Node* child : node->children) { // the value is deducted as a child node. value_sum -= child->val; } } // the value of the root node is `value_sum` for (Node* node : tree) { if (node->val == value_sum) { return node; } } return nullptr; } };

class Solution { /** * @param {_Node[]} tree * @return {_Node} */ findRoot(tree) { let value_sum = 0; for (let node of tree) { // the value is added as a parent node value_sum += node.val; for (let child of node.children) { // the value is deducted as a child node. value_sum -= child.val; } } // the value of the root node is `value_sum` for (let node of tree) { if (node.val === value_sum) { return node; } } return null; } }

public class Solution { public Node FindRoot(List<Node> tree) { int valueSum = 0; foreach (Node node in tree) { // the value is added as a parent node valueSum += node.val; foreach (Node child in node.children) { // the value is deducted as a child node. valueSum -= child.val; } } // the value of the root node is `valueSum` foreach (Node node in tree) { if (node.val == valueSum) { return node; } } return null; } }

func findRoot(tree []*Node) *Node { valueSum := 0 for _, node := range tree { // the value is added as a parent node valueSum += node.Val for _, child := range node.Children { // the value is deducted as a child node. valueSum -= child.Val } } // the value of the root node is `valueSum` for _, node := range tree { if node.Val == valueSum { return node } } return nil }

class Solution { fun findRoot(tree: List<Node>): Node? { var valueSum = 0 for (node in tree) { // the value is added as a parent node valueSum += node.`val` for (child in node.children) { // the value is deducted as a child node. valueSum -= child.`val` } } // the value of the root node is `valueSum` for (node in tree) { if (node.`val` == valueSum) { return node } } return null } }

class Solution { func findRoot(_ tree: [Node]) -> Node? { var valueSum = 0 for node in tree { // the value is added as a parent node valueSum += node.val for child in node.children { // the value is deducted as a child node. valueSum -= child.val } } // the value of the root node is `valueSum` for node in tree { if node.val == valueSum { return node } } return nil } }

impl Solution { pub fn find_root(tree: Vec<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> { let mut value_sum: i32 = 0; for node in &tree { value_sum += node.borrow().val; for child in &node.borrow().children { value_sum -= child.borrow().val; } } for node in &tree { if node.borrow().val == value_sum { return Some(node.clone()); } } None } }

复杂度分析

• 时间复杂度：O(N)。同样只需两次线性扫描；
• 空间复杂度：O(1)。只使用一个整数累加器，不借助任何集合或映射。

其中 N 为输入列表的长度，即 N 叉树的节点总数。

原理验证示例

假设树结构为：根节点值 1，子节点值 2、3；节点 2 的子节点值 4。输入列表乱序为[node(2), node(1), node(3), node(4)]（省略引用，仅示意值）：

最终valueSum = 1，恰好等于根节点值，随后在线性扫描中找到值为 1 的节点返回。可见求和过程将非根节点全部抵消，仅留下根节点。

两种解法对比与选型建议

选型建议：面试中若时间充裕，先讲哈希集合法（思路直观、不易出错），再补充求和抵消法展示对空间复杂度的优化意识；若题目明确要求 O(1) 空间或节点值域很小，直接采用求和抵消法。

常见陷阱与避坑指南

陷阱一：混淆节点值与节点引用

构建子节点集合时，可以存节点的val，也可以存节点对象引用本身。但必须前后一致：

• 存值，则在寻找根节点时比较值（seen.contains(node.val)）；
• 存引用，则比较引用（seen.contains(node)）。

混用会导致集合永远匹配不上，返回错误结果。仓库各语言实现统一采用"存值"策略，就是为了保证一致性。

陷阱二：假设根节点一定在列表索引 0

输入列表乱序给出，既非层序也非任何遍历序。永远不要假设根节点在列表首位，也不要提前 break 跳过扫描——必须完整遍历所有节点，找出那个"从未作为任何节点子节点"的节点。这正是两种解法都采用两遍完整扫描的原因。

陷阱三：求和抵消法的整数溢出

使用 O(1) 空间的求和解法时，valueSum在中间过程中可能累积很大的绝对值（例如所有父节点值相加、再减去所有子节点值），远超过最终结果。在 C/C++/Java/Go/Rust/Swift/Kotlin/C# 等定长整数语言中，极端情况下（节点数量巨大、节点值巨大）可能先溢出再"偶然"抵消回正确值，导致不可靠结果。规避方式：

• 优先使用足够宽的类型（如long/i64/Int64）；
• 若题目值域与节点规模可能触发溢出，改用哈希集合法更安全；
• Python 与 JavaScript（Number 采用 IEEE 754 双精度，整数安全范围 ±2^53）在常规数据规模下基本无需担心，但也不应盲目依赖。

陷阱四：忘记处理空列表 / 空树

若输入列表为空，两种解法都应当返回空结果（null/nil/None）。从各语言实现看，Java/C++/Go/Kotlin/Swift/Rust 均通过返回空值兜底，Python 实现则依赖"找不到匹配节点时自然结束"，实际刷题时应结合题目约束确认输入是否非空。

深入理解：这类"找根/找源"问题的通用思维

本问题的解法思维可以推广到更广的场景：

• 有向图找源节点：类似地，"入度为 0"的节点就是源节点（对应本题"从不作为子节点"）；
• 序列化/反序列化恢复树：当给定全部节点但缺失父子指针顺序时，本解法可辅助重建根节点，与仓库中的 serialize-and-deserialize-n-ary-tree.md 互为补充；
• 树/图的结构校验：利用"除根外每个节点入度恰为 1"的性质，可以顺便检测输入是否构成合法的树。

仓库中还收录了其他 N 叉树题解，可对照学习：克隆 N 叉树（clone-n-ary-tree.md）、N 叉树后序遍历（n-ary-tree-postorder-traversal.md）、N 叉树直径（diameter-of-n-ary-tree.md）、N 叉树与二叉树互转（encode-n-ary-tree-to-binary-tree.md）。

小结

"Find Root of N-Ary Tree" 是一道考察树结构性质洞察力与空间复杂度优化的经典题目：

1. 核心事实一句话：根节点是唯一从未出现在任何节点 children 列表中的节点；
2. O(N) 空间解法：哈希集合收集所有子节点值，两次扫描定位根节点，思路直接、实现稳妥；
3. O(1) 空间解法：利用"父加子减、非根节点两两抵消"的求和技巧，仅凭一个整数即可确定根节点值，是面试中展示优化思维的加分项；
4. 实战注意：保持值/引用判断一致、不假设根在首位、警惕求和法的整数溢出。

掌握这两种解法与陷阱分析，你就能在面试中游刃有余地应对这一类"乱序结构恢复"问题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode