這題給的是「每個節點對應父節點」的表示方式，要求判斷是否為合法樹。演算法本身不難，但面試重點是邏輯是否完整。
題意重述
給定長度為 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 沒做重複訪問判定
- 邊方向處理混亂，導致判定錯誤
- 忽略單節點等邊界情況
一句話總結
這題關鍵是把樹的條件講完整：唯一根、無重複路徑訪問、全節點可達。
需要輔助的同學隨時 dd 哦。
#googlevo #vo #北美求職 #sde求職 #ng求職 #北美找工 #留學生找工作 #求職輔導
延伸閱讀（外鏈）
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。
聯繫方式
Email: [email protected]
Telegram: @OAVOProxy