这题给的是“每个节点的父节点”表示法，目标是判断这是不是一棵合法树。题不难，但很看你能不能把判定条件讲清楚。
题意重述
给定一个长度为 n 的数组 parent：
parent[i]表示节点i的父节点- 根节点一般用特殊值表示（如
-1）
判断这组关系是否构成一棵合法树。
面试话术（可直接说）
我会用“结构合法 + 连通无环”来判定：
树必须有且只有一个根节点
先统计parent[i] == -1的数量。不是 1 直接返回false。从根节点出发，所有点都应该只被访问一次
我先根据parent建邻接表（父到子），再从根 DFS。
DFS 过程中用visited标记访问状态，如果某点被重复访问，说明存在非法结构（可视作环或多父路径），直接false。DFS 结束后必须全覆盖
检查是否每个节点都被访问到。若有未访问点，说明图不连通，返回false。
全部访问到才返回true。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(n)（邻接表 + visited）
容易错的点
- 只检查根节点数量，没检查全覆盖
- DFS 没做重复访问判定
- 把“父节点数组”当无向边处理，导致判定混乱
- 忽略空输入或单节点边界情况
一句话总结
这题本质不是“写个 DFS”就完了，而是把树的三个条件说完整：唯一根、无重复路径、全节点可达。
需要辅助的同学随时 dd 哦。
#googlevo #vo #北美求职 #sde求职 #ng求职 #北美找工 #留学生找工作 #求职辅导
延伸阅读（外链）
需要面试真题？ 立刻联系微信 Coding0201，获取真题。
联系方式
Email: [email protected]
Telegram: @OAVOProxy