1361 Validate Binary Tree Nodes 验证二叉树
Description:
You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild and rightChild, 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 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:
Example 1:
[图片上传失败...(image-3f51fc-1666796845160)]
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true
Example 2:
[图片上传失败...(image-15a661-1666796845160)]
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false
Example 3:
[图片上传失败...(image-5f0306-1666796845160)]
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false
Constraints:
n == leftChild.length == rightChild.length
1 <= n <= 10^4
-1 <= leftChild, rightChild <= n - 1
标题描述：
二叉树上有 n 个节点，按从 0 到 n - 1 编号，此中节点 i 的两个子节点分别是 leftChild 和 rightChild。
只有 全部 节点可以或许形成且 只 形成 一颗 有用的二叉树时，返回 true；否则返回 false。
假如节点 i 没有左子节点，那么 leftChild 就即是 -1。右子节点也符合该规则。
留意：节点没有值，本标题中仅仅使用节点编号。
示例：
示例 1：
[图片上传失败...(image-a76ef9-1666796845160)]
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true
示例 2：
[图片上传失败...(image-982e62-1666796845160)]
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出：false
示例 3：
[图片上传失败...(image-e519b5-1666796845160)]
输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false
示例 4：
[图片上传失败...(image-7edffa-1666796845160)]
输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
输出：false
提示：
1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild, rightChild <= n - 1
思绪：
BFS
通过盘算入度找到入度为 0 的节点, 该结点大概为根结点
从根结点出发, 层序遍历整个二叉树
假如没有环竣事循环
末了比力遍历过的结点数和 n 的巨细
时间复杂度为 O(n), 空间复杂度为 O(n)
代码:
C++: |
