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

Rust Solution

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
    );
}

Having problems with this solution? Click here to submit an issue on github.