1361. Validate Binary Tree Nodes

leetcode easy

#array#csharp#easy#graph#hash-table#leetcode#queue#search#tree#two-pointers

Task

У вас есть 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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

auto-draft, review before submit

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 solution

matched/original

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
}

Explanation

Algorithm

1⃣Проверка количества родителей для каждого узла:

Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

2⃣Поиск корневого узла и проверка на единственное дерево:

Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:

Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.

😎