1361. Validate Binary Tree Nodes
У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.
Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.
Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.
Пример
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class Solution {
public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
int[] parents = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
if (++parents[leftChild[i]] > 1) {
return false;
}
}
if (rightChild[i] != -1) {
if (++parents[rightChild[i]] > 1) {
return false;
}
}
}
int root = -1;
for (int i = 0; i < n; i++) {
if (parents[i] == 0) {
if (root == -1) {
root = i;
} else {
return false;
}
}
}
if (root == -1) {
return false;
}
HashSet<int> visited = new HashSet<int>();
Queue<int> queue = new Queue<int>();
queue.Enqueue(root);
while (queue.Count > 0) {
int node = queue.Dequeue();
if (!visited.Add(node)) {
return false;
}
if (leftChild[node] != -1) {
queue.Enqueue(leftChild[node]);
}
if (rightChild[node] != -1) {
queue.Enqueue(rightChild[node]);
}
}
return visited.Count == n;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool ValidateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int>& parents = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
if (++parents[leftChild[i]] > 1) {
return false;
}
}
if (rightChild[i] != -1) {
if (++parents[rightChild[i]] > 1) {
return false;
}
}
}
int root = -1;
for (int i = 0; i < n; i++) {
if (parents[i] == 0) {
if (root == -1) {
root = i;
} else {
return false;
}
}
}
if (root == -1) {
return false;
}
HashSet<int> visited = new HashSet<int>();
queue<int> queue = new queue<int>();
queue.Enqueue(root);
while (queue.size() > 0) {
int node = queue.Dequeue();
if (!visited.push_back(node)) {
return false;
}
if (leftChild[node] != -1) {
queue.Enqueue(leftChild[node]);
}
if (rightChild[node] != -1) {
queue.Enqueue(rightChild[node]);
}
}
return visited.size() == n;
}
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
public boolean ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
int[] parents = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) {
if (++parents[leftChild[i]] > 1) {
return false;
}
}
if (rightChild[i] != -1) {
if (++parents[rightChild[i]] > 1) {
return false;
}
}
}
int root = -1;
for (int i = 0; i < n; i++) {
if (parents[i] == 0) {
if (root == -1) {
root = i;
} else {
return false;
}
}
}
if (root == -1) {
return false;
}
HashSet<int> visited = new HashSet<int>();
Queue<int> queue = new LinkedList<int>();
queue.Enqueue(root);
while (queue.size() > 0) {
int node = queue.poll();
if (!visited.add(node)) {
return false;
}
if (leftChild[node] != -1) {
queue.Enqueue(leftChild[node]);
}
if (rightChild[node] != -1) {
queue.Enqueue(rightChild[node]);
}
}
return visited.size() == n;
}
}Go решение
сопоставлено/оригиналpackage main
import (
"fmt"
)
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
parents := make([]int, n)
for i := 0; i < n; i++ {
if leftChild[i] != -1 {
parents[leftChild[i]]++
if parents[leftChild[i]] > 1 {
return false
}
}
if rightChild[i] != -1 {
parents[rightChild[i]]++
if parents[rightChild[i]] > 1 {
return false
}
}
}
root := -1
for i := 0; i < n; i++ {
if parents[i] == 0 {
if root == -1 {
root = i
} else {
return false
}
}
}
if root == -1 {
return false
}
visited := make(map[int]struct{})
queue := []int{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if _, found := visited[node]; found {
return false
}
visited[node] = struct{}{}
if leftChild[node] != -1 {
queue = append(queue, leftChild[node])
}
if rightChild[node] != -1 {
queue = append(queue, rightChild[node])
}
}
return len(visited) == n
}
func main() {
leftChild := []int{1, -1, 3, -1}
rightChild := []int{2, -1, -1, -1}
fmt.Println(validateBinaryTreeNodes(4, leftChild, rightChild)) // Output: true
}Algorithm
1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.
2⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.
3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.