Manjusaka

10-17 leetcode 1361

链接 1361. Validate Binary Tree Nodes

题目

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], 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[i] 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.

题解

这题很简单

1. 用入度来判定 root 节点
2. 根据 root 节点遍历一次，然后看能否遍历所有节点

from collections import deque


class Solution:
    def validateBinaryTreeNodes(
        self, n: int, leftChild: list[int], rightChild: list[int]
    ) -> bool:
        in_degree = [0] * n
        for x, y in zip(leftChild, rightChild):
            if x != -1:
                in_degree[x] += 1
            if y != -1:
                in_degree[y] += 1
        roots = list(filter(lambda x: in_degree[x] == 0, range(n)))
        if len(roots) != 1:
            return False
        visited = set()
        queue = deque([roots[0]])
        while queue:
            node = queue.popleft()
            if node in visited:
                return False
            visited.add(node)
            if leftChild[node] != -1:
                queue.append(leftChild[node])
            if rightChild[node] != -1:
                queue.append(rightChild[node])
        return len(visited) == n