LeetCode 补充题 163. 根据父子关系构建森林
题目描述
给定节点记录
(id,parentId)，其中id唯一且为正数，parentId=0表示根节点。保证所有非零父节点存在，父子关系无环。返回森林的根节点列表，根节点及同级孩子按输入顺序排列。
示例 1：
输入：
records = [[2,1],[1,0],[3,0],[4,1]]
输出：[{"id":1,"children":[{"id":2,"children":[]},{"id":4,"children":[]}]},{"id":3,"children":[]}]
解释： 每条记录为[id,parentId]。1、3 是根，2、4 是 1 的孩子；根及孩子均按输入中的相对顺序排列。
提示：
-
id为唯一正整数，parentId=0表示根。 - 保证非零父节点存在且无环。
- 根节点及同级孩子按输入顺序排列。
题意分析
父节点可能出现在孩子记录之后，单遍遇到孩子就查找父节点会失败。先创建全部节点，再按关系挂接，可以将对象创建与顺序连接分开，避免重复创建同一节点。
解法：先建 id 映射再按顺序挂接
核心思路
[!blue]
第一遍按唯一
id创建节点并存入映射，使任何非零父编号在第二遍都能直接找到。映射中的对象就是最终森林里的对象，后续只添加引用，不复制子树。第二遍严格按照原记录顺序：
parentId == 0的节点追加到根列表，其余追加到父节点的children。每个节点恰好挂接一次，根和每组同级孩子的相对顺序都由追加顺序保证。题面已保证父节点存在且无环，因此无需额外搜索或把异常节点当成根。空记录返回空森林；不要改为遍历哈希表挂接，否则无法保证顺序。
解题步骤
- 第一遍按每个 id 创建唯一节点，全部放入映射。
- 第二遍仍按原输入顺序处理记录，根加入根列表，其他节点加入对应父亲的 children。
- 返回根列表，不把孤儿或环偷偷当作额外根。
代码实现
class Node {
final int id;
final List<Node> children = new ArrayList<>();
Node(int id) {
this.id = id;
}
}
class Solution {
public List<Node> forest(int[][] records) {
Map<Integer, Node> nodes = new HashMap<>();
for (int[] record : records) {
nodes.put(record[0], new Node(record[0]));
}
List<Node> roots = new ArrayList<>();
for (int[] record : records) {
Node node = nodes.get(record[0]);
if (record[1] == 0) {
roots.add(node);
} else {
nodes.get(record[1]).children.add(node);
}
}
return roots;
}
}
type Node struct {
ID int
Children []*Node
}
func forest(records [][]int) []*Node {
nodes := map[int]*Node{}
for _, record := range records {
nodes[record[0]] = &Node{ID: record[0]}
}
roots := []*Node{}
for _, record := range records {
node := nodes[record[0]]
if record[1] == 0 {
roots = append(roots, node)
} else {
parent := nodes[record[1]]
parent.Children = append(parent.Children, node)
}
}
return roots
}
复杂度分析
- 时间复杂度：期望 $O(n)$。
- 空间复杂度：节点与映射空间 $O(n)$。
关键点总结
[!green]
先建齐节点再连边，使父记录可以晚于孩子出现；根列表及每个父节点的 children 均按输入次序追加。
易错点总结
[!yellow]
本题输入是已校验的森林关系；孤儿节点、重复id和环不是默认根节点，接收外部数据时应先校验这些约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2196. 根据描述创建二叉树 | 中等 | 同样从父子描述创建节点关系，本题允许多个根且用 parentId=0 显式标识根。 |
| 133. 克隆图 | 中等 | 都需要映射保证每个身份只创建一个节点；本题按 id 挂接，克隆图按原节点对象复用克隆节点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！