Leetcode 1361:验证二叉树(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1361:验证二叉树(超详细的解法!!!)

in leetcode with 0 comment

二叉树上有 n 个节点,按从 0n - 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

提示:

解题思路

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

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

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: reutrn False
        root = i

if 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://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879?fr=aladdin

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

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses