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.
1public class 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 bool Union(int[] parent, int x, int y) {
10 int rootX = Find(parent, x);
11 int rootY = Find(parent, y);
12 if (rootX == rootY) return false;
13 parent[rootY] = rootX;
14 return true;
15 }
16
17 public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
18 int[] parent = new int[n];
19 int[] hasParent = new int[n];
20 for (int i = 0; i < n; ++i) parent[i] = i;
21
22 for (int i = 0; i < n; ++i) {
23 if (leftChild[i] != -1) {
24 if (hasParent[leftChild[i]] == 1 || !Union(parent, i, leftChild[i])) {
25 return false;
26 }
27 hasParent[leftChild[i]] = 1;
28 }
29 if (rightChild[i] != -1) {
30 if (hasParent[rightChild[i]] == 1 || !Union(parent, i, rightChild[i])) {
31 return false;
32 }
33 hasParent[rightChild[i]] = 1;
34 }
35 }
36
37 int rootCount = 0;
38 for (int i = 0; i < n; ++i) {
39 if (hasParent[i] == 0) {
40 rootCount++;
41 }
42 }
43
44 return rootCount == 1;
45 }
46}The C# implementation mirrors other union-find solutions, modifying the state intelligently between nodes. Components track their leaders (or roots) through recursion and path compression in Find and are unified via Union. Constraints enforce at most one parent per node via a check through hasParent, ensuring single connectivity by requiring one and only one root.
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.
1class Solution {
2 private void dfs(int node, boolean[] visited, int[][] children) {
3 if (visited[node]) return;
4 visited[node] = true;
5 if (children[0][node] != -1) dfs(children[0][node], visited, children);
6 if (children[1][node] != -1) dfs(children[1][node], visited, children);
7 }
8
9 public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
10 int[] inDegree = new int[n];
11 int root = -1;
12
13 for (int i = 0; i < n; ++i) {
14 if (leftChild[i] != -1) inDegree[leftChild[i]]++;
15 if (rightChild[i] != -1) inDegree[rightChild[i]]++;
16 }
17
18 for (int i = 0; i < n; ++i) {
19 if (inDegree[i] == 0) {
20 if (root == -1) {
21 root = i;
22 } else {
23 return false;
24 }
25 }
26 }
27
28 if (root == -1) return false;
29
30 boolean[] visited = new boolean[n];
31 dfs(root, visited, new int[][]{leftChild, rightChild});
32
33 for (boolean v : visited) {
34 if (!v) return false;
35 }
36
37 return true;
38 }
39}The Java version checks for a single node with inDegree zero, identifying it as the root. Nodes are structured as positions within two arrays/lists representing binary tree branches. The DFS aims to explore all nodes in one pass, validating complete connectivity without omitted nodes.