1361-validate-binary-tree-nodes.rb

# frozen_string_literal: true

# 1361. Validate Binary Tree Nodes
# Medium
# https://leetcode.com/problems/validate-binary-tree-nodes

=begin
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
=end

# @param {Integer} n
# @param {Integer[]} left_child
# @param {Integer[]} right_child
# @return {Boolean}
defvalidate_binary_tree_nodes(n,left_child,right_child)
parents,children=[],Array.new(n){ |_| Array.new}
[left_child,right_child].eachdo |childs|
childs.each_with_indexdo |c,i|
nextifc.negative?
parents[c] ||= i
returnfalseifparents[c] != i
returnfalseifchildren[i].include?(c)
children[i] << c
end
end

returnfalseunlessn.times.collect{ |p| parents[p].nil? ? 1 : 0}.sum == 1

root=n.times.inject(nil)do |r,p|
returnfalseifparents[p].nil? && !r.nil?
parents[p].nil? ? p : r
end
visited,cur=Set[root],Set[root]
untilcur.empty?do
cur=cur.inject(Set[])do |r,c|
cc=children[c]
returnfalseifcc.any?{ |ccc| visited.include?(ccc)}
visited.merge(cc)
r.merge(cc)
end
end

visited.size == n
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_validate_binary_tree_nodes < Test::Unit::TestCase
deftest_
assert_equaltrue,validate_binary_tree_nodes(4,[1, -1,3, -1],[2, -1, -1, -1])
assert_equalfalse,validate_binary_tree_nodes(4,[1, -1,3, -1],[2,3, -1, -1])
assert_equalfalse,validate_binary_tree_nodes(4,[1,0],[-1, -1])
end
end