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.
1#include <vector>
2#include <unordered_set>
3
4class DSU {
5 std::vector<int> parent;
6public:
7 DSU(int n) {
8 parent.resize(n);
9 for (int i = 0; i < n; ++i) parent[i] = i;
10 }
11
12 int find(int x) {
13 if (parent[x] != x)
14 parent[x] = find(parent[x]);
15 return parent[x];
16 }
17
18 bool unionSets(int x, int y) {
19 int rootX = find(x), rootY = find(y);
20 if (rootX == rootY) return false;
21 parent[rootY] = rootX;
22 return true;
23 }
24};
25
26bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
27 DSU dsu(n);
28 std::vector<int> inDegree(n, 0);
29
30 for (int i = 0; i < n; ++i) {
31 if (leftChild[i] != -1) {
32 if (++inDegree[leftChild[i]] > 1 || !dsu.unionSets(i, leftChild[i]))
33 return false;
34 }
35 if (rightChild[i] != -1) {
36 if (++inDegree[rightChild[i]] > 1 || !dsu.unionSets(i, rightChild[i]))
37 return false;
38 }
39 }
40
41 int rootCount = 0;
42 for (int i = 0; i < n; ++i) {
43 if (dsu.find(i) == i) ++rootCount;
44 }
45
46 return rootCount == 1;
47}This C++ solution is a close variant of the C example. It uses a class DSU structuring the union-find operations. The solution primarily checks for:
Vector inDegree tracks in-degrees, and the DSU tracks roots. After processing all nodes, the algorithm checks the single connected component from the root count.
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 def dfs(self, node, visited, children):
3 if visited[node]: return
4 visited[node] = True
5 if children[0][node] != -1:
6 self.dfs(children[0][node], visited, children)
7 if children[1][node] != -1:
8 self.dfs(children[1][node], visited, children)
9
10 def validateBinaryTreeNodes(self, n, leftChild, rightChild):
11 # Calculate in-degrees
12 inDegree = [0] * n
13 for i in range(n):
14 if leftChild[i] != -1:
15 inDegree[leftChild[i]] += 1
16 if rightChild[i] != -1:
17 inDegree[rightChild[i]] += 1
18
19 root = -1
20 for i in range(n):
21 if inDegree[i] == 0:
22 if root == -1:
23 root = i
24 else:
25 return False
26
27 if root == -1:
28 return False
29
30 visited = [False] * n
31 self.dfs(root, visited, [leftChild, rightChild])
32
33 return all(visited)The Python strategem frames nodes as tuples within a list structure, exploiting recognized semantics over positions within binary arrays (left and right children). Node in-degrees determine the hierarchy without multi-parents obstruction, generating a singular possible valid root. DFS confirms full graph traversability from the root node, ensuring a connected nature without interruptions.