There are n nodes labeled from 0 through n - 1. For each node i, leftChild[i] and rightChild[i] give the labels of its children. A child entry of -1 means that child is absent.
Return true exactly when these links form one valid binary tree containing all n nodes. Such a tree has one root with no parent, every other node has exactly one parent, and following child links from the root reaches every node without a cycle. Otherwise return false.
The root can have any label; it does not have to be node 0. The arrays describe links by node label, not level-order traversal or node values.
Edges labeled L and R identify left and right children.
Example 1:
Input: n = 3
leftChild = [-1,-1,0]
rightChild = [-1,-1,1]
Output: trueExplanation: Node 2 is the root, with left child 0 and right child 1. Both children are leaves, and all three nodes belong to this one tree. A valid root need not have label 0.
Example 2:
Input: n = 3
leftChild = [1,-1,-1]
rightChild = [2,2,-1]
Output: falseExplanation: Node 2 is listed as a child of both node 0 and node 1. A non-root node must have exactly one parent, so these links are invalid.
Example 3:
Input: n = 3
leftChild = [1,0,-1]
rightChild = [-1,-1,-1]
Output: falseExplanation: Nodes 0 and 1 point to each other, forming a cycle. Node 2 is isolated. The links therefore do not form one tree containing all nodes.
Constraints:
1 <= n <= 10000leftChild.length == rightChild.length == n-1 <= leftChild[i], rightChild[i] < n