To solve this problem using the Disjoint Set Union (DSU) approach, we aim to union nodes based on their parent-child relationships. A valid tree should follow these rules:
Time Complexity: O(n), where n is the number of nodes, due to each union and find operation being nearly constant with path compression.
Space Complexity: O(n) for the parent array.
1class Solution {
2 public int find(int[] parent, int x) {
3 if (parent[x] != x) {
4 parent[x] = find(parent, parent[x]);
5 }
6 return parent[x];
7 }
8
9 public boolean unionFind(int[] parent, int x, int y) {
10 int rootX = find(parent, x);
11 int rootY = find(parent, y);
12
13 if (rootX == rootY) return false;
14 parent[rootY] = rootX;
15 return true;
16 }
17
18 public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
19 int[] parent = new int[n];
20 int[] hasParent = new int[n];
21 for (int i = 0; i < n; ++i) {
22 parent[i] = i;
23 }
24
25 for (int i = 0; i < n; ++i) {
26 if (leftChild[i] != -1) {
27 if (hasParent[leftChild[i]] == 1 || !unionFind(parent, i, leftChild[i])) {
28 return false;
29 }
30 hasParent[leftChild[i]] = 1;
31 }
32 if (rightChild[i] != -1) {
33 if (hasParent[rightChild[i]] == 1 || !unionFind(parent, i, rightChild[i])) {
34 return false;
35 }
36 hasParent[rightChild[i]] = 1;
37 }
38 }
39
40 int rootCount = 0;
41 for (int i = 0; i < n; ++i) {
42 if (hasParent[i] == 0) {
43 rootCount++;
44 }
45 }
46
47 return rootCount == 1;
48 }
49}This Java solution, similar in logic to the C and C++ solutions, uses a union-find structure managed through unionFind and find methods. The hasParent array manages in-degree checks to ensure a single parent per node, avoiding tree invalidation by multiple roots or cycles. After scanning nodes, it confirms just one root using hasParent.
This approach involves calculating the in-degree of each node and checking connectivity via a DFS. The key aspects of a tree like single-root presence and cycle-checking can be managed by:
Time Complexity: O(n), since each node and its immediate edges are evaluated once in each step, including in-drives calculations and DFS.
Space Complexity: O(n) for holding visited tracking and in-degree counts.
1#include <vector>
2
3void dfs(int node, std::vector<bool>& visited, std::vector<std::vector<int>>& adj) {
4 if (visited[node]) return;
5 visited[node] = true;
6 for (int child : adj[node]) {
7 dfs(child, visited, adj);
8 }
9}
10
11bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
12 std::vector<int> inDegree(n, 0);
13 std::vector<std::vector<int>> adj(n);
14
15 for (int i = 0; i < n; ++i) {
16 if (leftChild[i] != -1) {
17 adj[i].push_back(leftChild[i]);
18 inDegree[leftChild[i]]++;
19 }
20 if (rightChild[i] != -1) {
21 adj[i].push_back(rightChild[i]);
22 inDegree[rightChild[i]]++;
23 }
24 }
25
26 int root = -1;
27 for (int i = 0; i < n; ++i) {
28 if (inDegree[i] == 0) {
29 if (root == -1) {
30 root = i;
31 } else {
32 return false;
33 }
34 }
35 }
36
37 if (root == -1) return false;
38
39 std::vector<bool> visited(n, false);
40 dfs(root, visited, adj);
41
42 for (auto v : visited) {
43 if (!v) return false;
44 }
45 return true;
46}This solution represents each node and its relationships as directed graph edges, forming an adjacency list adj. It begins by resolving in-degrees to locate the root. The dfs ensures all nodes are explored from the root, confirming all nodes are part of a single, adequately connected component with single ingress from the root.