1361. Validate Binary Tree Nodes

题目信息

题号:

1361

难度:

Medium

主题:

图、二叉树、入度、连通性

原题:

LeetCode 1361

重点:

所有节点必须恰好组成一棵二叉树:唯一根、非根入度为一、无环且全部连通

题目重述

有 n 个节点,编号 0 到 n-1。leftChild[i] 和 rightChild[i] 分别给出节点 i 的左右孩子,-1 表示不存在。

请判断这些关系是否恰好构成一棵包含全部节点的二叉树。任何节点不能有两个父节点,必须有且仅有一个根,并且从根能够访问所有节点且不存在环。

1 <= n <= 10^4,孩子编号为 -1 或合法节点下标。

自建示例

唯一根可访问全部节点:

输入:n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出:true
解释:节点 0 为根,左右孩子为 1、2,节点 2 的左孩子为 3。

同一节点有两个父节点时无效:

输入:n = 3, leftChild = [1,-1,-1], rightChild = [2,2,-1]
输出:false
解释:节点 2 同时是节点 0 和节点 1 的右孩子。