Welcome to Subscribe On Youtube
1361. Validate Binary Tree Nodes
Description
You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.
If node i has no left child then leftChild[i] will equal -1, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
Example 1:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true
Example 2:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false
Example 3:
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false
Constraints:
n == leftChild.length == rightChild.length1 <= n <= 104-1 <= leftChild[i], rightChild[i] <= n - 1
Solutions
Solution 1: Union-Find
We can traverse each node $i$ and its corresponding left and right children $l$, $r$, using an array $vis$ to record whether the node has a parent:
- If the child node already has a parent, it means there are multiple fathers, which does not meet the condition, so we return
falsedirectly. - If the child node and the parent node are already in the same connected component, it means a cycle will be formed, which does not meet the condition, so we return
falsedirectly. - Otherwise, we perform a union operation, set the corresponding position of the $vis$ array to
true, and decrease the number of connected components by $1$.
After the traversal, we check whether the number of connected components in the union-find set is $1$. If it is, we return true, otherwise, we return false.
The time complexity is $O(n \times \alpha(n))$, and the space complexity is $O(n)$. Where $n$ is the number of nodes, and $\alpha(n)$ is the inverse Ackermann function, which is less than $5$.
Solution 2: Indegree Counting + BFS
We can first count the indegree of each node, i.e., how many parents point to it. If there is no node with indegree $0$, it means there is a cycle in the graph, so we return false directly; otherwise, that node is the root.
Next, we perform a breadth-first search starting from the root. During the traversal, if a child node has already been visited, it means the node has multiple parents or there is a cycle in the graph, so we return false directly.
After the traversal, we check whether the number of visited nodes equals $n$. If so, all nodes form exactly one valid binary tree and we return true; otherwise, we return false.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes.
-
class Solution { private int[] p; public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) { p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } boolean[] vis = new boolean[n]; for (int i = 0, m = n; i < m; ++i) { for (int j : new int[] {leftChild[i], rightChild[i]}) { if (j != -1) { if (vis[j] || find(i) == find(j)) { return false; } p[find(i)] = find(j); vis[j] = true; --n; } } } return n == 1; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } // Solution 2 class Solution { public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) { int[] indeg = new int[n]; for (int c : leftChild) { if (c != -1) { indeg[c]++; } } for (int c : rightChild) { if (c != -1) { indeg[c]++; } } int root = -1; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { root = i; break; } } if (root == -1) { return false; } Deque<Integer> q = new ArrayDeque<>(); q.add(root); Set<Integer> vis = new HashSet<>(); vis.add(root); while (!q.isEmpty()) { int i = q.poll(); int j = leftChild[i]; if (j != -1) { if (vis.contains(j)) { return false; } vis.add(j); q.add(j); } j = rightChild[i]; if (j != -1) { if (vis.contains(j)) { return false; } vis.add(j); q.add(j); } } return vis.size() == n; } } -
class Solution { public: bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) { int p[n]; iota(p, p + n, 0); bool vis[n]; memset(vis, 0, sizeof(vis)); function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); }; for (int i = 0, m = n; i < m; ++i) { for (int j : {leftChild[i], rightChild[i]}) { if (j != -1) { if (vis[j] || find(i) == find(j)) { return false; } p[find(i)] = find(j); vis[j] = true; --n; } } } return n == 1; } }; // Solution 2 class Solution { public: bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) { vector<int> indeg(n, 0); for (int c : leftChild) { if (c != -1) { indeg[c]++; } } for (int c : rightChild) { if (c != -1) { indeg[c]++; } } int root = -1; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { root = i; break; } } if (root == -1) { return false; } queue<int> q; unordered_set<int> vis; q.push(root); vis.insert(root); while (!q.empty()) { int i = q.front(); q.pop(); int j = leftChild[i]; if (j != -1) { if (vis.count(j)) { return false; } vis.insert(j); q.push(j); } j = rightChild[i]; if (j != -1) { if (vis.count(j)) { return false; } vis.insert(j); q.push(j); } } return vis.size() == n; } }; -
class Solution: def validateBinaryTreeNodes( self, n: int, leftChild: List[int], rightChild: List[int] ) -> bool: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(n)) vis = [False] * n for i, (a, b) in enumerate(zip(leftChild, rightChild)): for j in (a, b): if j != -1: if vis[j] or find(i) == find(j): return False p[find(i)] = find(j) vis[j] = True n -= 1 return n == 1 # Solution 2 class Solution: def validateBinaryTreeNodes( self, n: int, leftChild: List[int], rightChild: List[int] ) -> bool: indeg = [0] * n for c in chain(leftChild, rightChild): if c != -1: indeg[c] += 1 root = next((i for i, x in enumerate(indeg) if x == 0), -1) if root == -1: return False q = deque([root]) vis = {root} while q: i = q.popleft() for j in (leftChild[i], rightChild[i]): if j != -1: if j in vis: return False vis.add(j) q.append(j) return len(vis) == n -
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool { p := make([]int, n) for i := range p { p[i] = i } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } vis := make([]bool, n) for i, a := range leftChild { for _, j := range []int{a, rightChild[i]} { if j != -1 { if vis[j] || find(i) == find(j) { return false } p[find(i)] = find(j) vis[j] = true n-- } } } return n == 1 } // Solution 2 func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool { indeg := make([]int, n) for _, c := range leftChild { if c != -1 { indeg[c]++ } } for _, c := range rightChild { if c != -1 { indeg[c]++ } } root := -1 for i, x := range indeg { if x == 0 { root = i break } } if root == -1 { return false } q := []int{root} vis := map[int]bool{root: true} for len(q) > 0 { i := q[0] q = q[1:] j := leftChild[i] if j != -1 { if vis[j] { return false } vis[j] = true q = append(q, j) } j = rightChild[i] if j != -1 { if vis[j] { return false } vis[j] = true q = append(q, j) } } return len(vis) == n }