1361. Validate Binary Tree Nodes

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

Example 4:

```Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false
```

Constraints:

• `1 <= n <= 104`
• `leftChild.length == rightChild.length == n`
• `-1 <= leftChild[i], rightChild[i] <= n - 1`

1361. Validate Binary Tree Nodes
``````struct Solution;

impl Solution {
fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
let n = n as usize;
let mut indegree = vec![0; n];
let mut outdegree = vec![0; n];
let mut edge = 0;
for i in 0..n {
if left_child[i] != -1 {
edge += 1;
outdegree[i] += 1;
indegree[left_child[i] as usize] += 1;
}
if right_child[i] != -1 {
edge += 1;
outdegree[i] += 1;
indegree[right_child[i] as usize] += 1;
}
}
let degree = (0..n).any(|i| {
let a = n != 1 && indegree[i] == 0 && outdegree[i] == 0;
let b = indegree[i] > 1;
let c = outdegree[i] > 2;
a || b || c
});
!degree && edge + 1 == n
}
}

#[test]
fn test() {
let n = 4;
let left_child = vec![1, -1, 3, -1];
let right_child = vec![2, -1, -1, -1];
let res = true;
assert_eq!(
Solution::validate_binary_tree_nodes(n, left_child, right_child),
res
);
let n = 4;
let left_child = vec![1, -1, 3, -1];
let right_child = vec![2, 3, -1, -1];
let res = false;
assert_eq!(
Solution::validate_binary_tree_nodes(n, left_child, right_child),
res
);
let n = 2;
let left_child = vec![1, 0];
let right_child = vec![-1, -1];
let res = false;
assert_eq!(
Solution::validate_binary_tree_nodes(n, left_child, right_child),
res
);
let n = 6;
let left_child = vec![1, -1, -1, 4, -1, -1];
let right_child = vec![2, -1, -1, 5, -1, -1];
let res = false;
assert_eq!(
Solution::validate_binary_tree_nodes(n, left_child, right_child),
res
);
}
``````