#1361

Validate Binary Tree Nodes

specialist · 975 · lc medium +32 · failed · 44.1% accepted · 2,249 likes · top 26%

⚑ DFS / BFS: Connected Components & Reachability

Description

You have n binary tree nodes numbered 0 to n - 1. Node i has leftChild[i] as its left child and rightChild[i] as its right child; -1 indicates no child. Return true if and only if all nodes together form a single valid binary tree. Note that nodes carry no values; only the numbering matters.

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

Code

1

2

3

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool: