1361. Validate Binary Tree Nodes¶
题目信息¶
- 题号:
1361
- 难度:
Medium
- 主题:
图、二叉树、入度、连通性
- 原题:
- 重点:
所有节点必须恰好组成一棵二叉树:唯一根、非根入度为一、无环且全部连通
题目重述¶
有 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 的右孩子。