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 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.