→ ZooseWu: 這題是1361 靠北 10/18 01:30
對不起
※ 編輯: Rushia (60.250.69.212 臺灣), 10/18/2023 15:10:48
1361. Validate Binary Tree Nodes
https://leetcode.com/problems/validate-binary-tree-nodes/description
給你一個數字 n 表示節點數量(編號為0 ~ n-1)，leftChild[i] 表示 i 的左節點，
rightChild[i]表示 i 的右節點，如果為-1表示沒有子節點，求出這些節點相連之後
是否是一棵二元樹，是的話返回 true，否則 false。
思路：
1.用併查集紀錄圖形的連通狀況。
2.用一個陣列記錄每個點的入度。
3.檢查：
(1) 每個點的入度小於等於一
(2) 圖形是連通圖
(3) 共有 n - 1 條路徑
如果都符合就返回 true。
Java Code：
-----------------------------------------
class Solution {
public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[]
rightChild) {
int[] root = new int[n];
for (int i = 0; i < n; i++) {
root[i] = i;
}
int[] in = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
merge(i, leftChild[i], root);
in[leftChild[i]]++;
}
if (rightChild[i] != -1) {
merge(i, rightChild[i], root);
in[rightChild[i]]++;
}
}
int cnt = in[0];
for (int i = 1; i < n; i++) {
if (find(i, root) != find(i - 1, root)) {
return false;
}
if (in[i] > 1) {
return false;
}
cnt += in[i];
}
return cnt == n - 1;
}
private int find(int x, int[] root) {
return x == root[x] ? x : (root[x] = find(root[x], root));
}
private void merge(int x, int y, int[] root) {
root[find(x, root)] = find(y, root);
}
}
-----------------------------------------
我好爛 暴力硬幹= =
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697551776.A.0AA.html