MediumRating 1465
1361. Validate Binary Tree Nodes
treedepth-first-searchbreadth-first-searchunion-findgraphbinary-tree
解題說明
Validate Binary Tree Nodes
題目描述： 給定 n 個節點（編號 0 到 n-1），以及兩個陣列 leftChild 和 rightChild 分別表示每個節點的左右子節點（-1 表示無子節點）。判斷這些節點是否恰好構成一棵有效的二元樹。
解題思路： 有效的二元樹需要滿足三個條件：(1) 恰好有一個根節點（入度為 0）；(2) 除根節點外每個節點恰好有一個父節點（入度為 1）；(3) 所有節點構成一個連通圖。首先計算每個節點的入度，找到唯一的根節點。然後從根節點出發做 BFS/DFS，驗證能訪問到所有 n 個節點。
C++ 解法
複雜度分析
時間複雜度：O(n) — 計算入度需 O(n)，BFS 遍歷需 O(n)
空間複雜度：O(n) — 入度陣列和 BFS 佇列
虛擬碼
1. Calculate indegree for each node from leftChild and rightChild arrays 2. If any node has indegree > 1, return false (multiple parents) 3. Find the root: the node with indegree 0 4. If no root or multiple roots exist, return false 5. BFS from root, count visited nodes 6. Return true if visited == n (all nodes connected)
其他解法
方法二：Union-Find 使用並查集，每次添加父子邊時合併兩個節點。如果兩個已在同一集合的節點嘗試合併，說明有環。最後檢查是否只有一個連通分量。時間複雜度 O(n × α(n))。
方法三：DFS 找到根節點後用 DFS 代替 BFS 遍歷。邏輯相同，只是遍歷方式不同。遞迴深度可能較大。
延伸思考
- 如果不限定為二元樹，而是可以有任意數量子節點的一般樹，驗證邏輯需要如何修改？
- 如果輸入可能包含自環（節點指向自己），你的解法能正確處理嗎？
- 如何修改演算法以回傳使其成為有效二元樹所需的最少修改次數？