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