LeetCode 1361. 验证二叉树

Categories:

题目描述
思路分析
1. 解法一：入度 + BFS 判树（推荐）
相似题目

题目描述

✅ 1361. 验证二叉树

思路分析

解法一：入度 + BFS 判树（推荐）

核心思路：

统计每个节点入度，若存在入度 > 1 则不合法。

根节点必须且仅有一个（入度为 0）。

从根节点 BFS，若出现重复访问或最终未遍历全部节点，则不是有效二叉树。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1 && ++indeg[leftChild[i]] > 1) {
                return false;
            }
            if (rightChild[i] != -1 && ++indeg[rightChild[i]] > 1) {
                return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                if (root != -1) {
                    return false;
                }
                root = i;
            }
        }
        if (root == -1) {
            return false;
        }

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(root);
        visited[root] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            int l = leftChild[cur];
            int r = rightChild[cur];
            if (l != -1) {
                if (visited[l]) {
                    return false;
                }
                visited[l] = true;
                queue.offer(l);
            }
            if (r != -1) {
                if (visited[r]) {
                    return false;
                }
                visited[r] = true;
                queue.offer(r);
            }
        }

        return count == n;
    }
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    indeg := make([]int, n)
    for i := 0; i < n; i++ {
        if leftChild[i] != -1 {
            indeg[leftChild[i]]++
            if indeg[leftChild[i]] > 1 {
                return false
            }
        }
        if rightChild[i] != -1 {
            indeg[rightChild[i]]++
            if indeg[rightChild[i]] > 1 {
                return false
            }
        }
    }

    root := -1
    for i := 0; i < n; i++ {
        if indeg[i] == 0 {
            if root != -1 {
                return false
            }
            root = i
        }
    }
    if root == -1 {
        return false
    }

    visited := make([]bool, n)
    queue := make([]int, 0)
    queue = append(queue, root)
    visited[root] = true
    count := 0

    for head := 0; head < len(queue); head++ {
        cur := queue[head]
        count++
        l := leftChild[cur]
        r := rightChild[cur]
        if l != -1 {
            if visited[l] {
                return false
            }
            visited[l] = true
            queue = append(queue, l)
        }
        if r != -1 {
            if visited[r] {
                return false
            }
            visited[r] = true
            queue = append(queue, r)
        }
    }

    return count == n
}

相似题目

题目	难度	考察点
261. 以图判树	中等	并查集
323. 无向图中连通分量的数目	中等	图遍历
207. 课程表	中等	拓扑
210. 课程表 II	中等	拓扑
1110. 删点成林	中等	树遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/47879271