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.length
1 <= n <= 104
-1 <= leftChild[i], rightChild[i] <= n - 1
Solution
validate-binary-tree-nodes.py
class Solution:
def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
inDegree = [0] * n
def countNodes(node):
if node == -1: return 0
return 1 + countNodes(leftChild[node]) + countNodes(rightChild[node])
for i, (left, right) in enumerate(zip(leftChild, rightChild)):
if left != -1:
if inDegree[left] == 1: return False
inDegree[left] += 1
if right != -1:
if inDegree[right] == 1: return False
inDegree[right] += 1
root = -1
for i in range(n):
if inDegree[i] == 0:
if root == -1:
root = i
else:
return False
return root != -1 and countNodes(root) == n
validate-binary-tree-nodes.cpp
class Solution {
public:
int countNodes(vector<int> &l,vector<int> &r,int root) // DFS from root to validate that all nodes are visited.
{
if(root==-1)
return 0;
return 1+countNodes(l,r,l[root])+countNodes(l,r,r[root]);
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild)
{
vector<int> inDegree(n,0);
int root=-1;
for(int i=0;i<leftChild.size();i++)
if(leftChild[i]!=-1&&inDegree[leftChild[i]]++==1) //If in-degree exceeds 1 return false.
return false;
else if(rightChild[i]!=-1&&inDegree[rightChild[i]]++==1) //If in-degree exceeds 1 return false.
return false;
for(int i=0;i<leftChild.size();i++) //Find root and also check for multiple roots.
if(inDegree[i]==0) //If in-degree = 0 and has children it's a root.
if(root==-1) //Store the root.
root=i;
else //We have multiple roots, return false
return false;
if(root==-1)
return false;
return countNodes(leftChild,rightChild,root)==n;
}
};