本文共 1866 字，大约阅读时间需要 6 分钟。

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。

只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。

如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。

注意：节点没有值，本问题中仅仅使用节点编号。

示例 1：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]输出：true

示例 2：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]输出：false

示例 3：

输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]输出：false

示例 4：

输入：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[i], rightChild[i] <= n - 1

解题思路

首先明确二叉树的定义：二叉树是一个连通的无环图，并且每一个顶点的度（包括入度和出度）不大于3，根结点的度不大于2。

所以先要确定树根，可以通过入度为0来确认。如果树根不存在自然就返回False了，如果存在多个树根同样返回False。

d = [0] * nfor i in leftChild + rightChild:    if i != -1: d[i] += 1        root = -1for i in range(n):    if d[i] == 0:        if root != -1: reutrn False        root = iif root == -1:    return False

然后就是判断连通性，可以通过bfs来判断是不是每个节点有且仅被访问一次。

class Solution:    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:        d = [0] * n        for i in leftChild + rightChild:            if i != -1: d[i] += 1                root = -1        for i in range(n):            if d[i] == 0:                if root != -1: return False                root = i        if root == -1: return False                vis, q = set([root]), [root]        while q:            pre = q.pop(0)            if leftChild[pre] != -1:                if leftChild[pre] in vis: return False                vis.add(leftChild[pre])                q.append(leftChild[pre])                        if rightChild[pre] != -1:                if rightChild[pre] in vis: return False                vis.add(rightChild[pre])                q.append(rightChild[pre])                return len(vis) == n

reference:

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104484482 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！