Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- List<List<Integer>> graph;
- int[] colors;
- public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
- graph = new ArrayList<>();
- colors = new int[n];
- int[] numParents = new int[n];
- // build graph
- for (int i = 0; i < n; i++) {
- graph.add(new ArrayList<>());
- }
- for (int i = 0; i < n; i++) {
- if (leftChild[i] != -1) {
- graph.get(i).add(leftChild[i]);
- graph.get(leftChild[i]).add(i);
- numParents[leftChild[i]]++;
- }
- if (rightChild[i] != -1) {
- graph.get(i).add(rightChild[i]);
- graph.get(rightChild[i]).add(i);
- numParents[rightChild[i]]++;
- }
- }
- // if there is a node with multiple parents, this is not a valid tree
- for (int i = 0; i < n; i++) {
- if (numParents[i] > 1) {
- return false;
- }
- }
- // check cycle
- hasCycleDfs(0);
- // there is unvisited node, the graph is not connected, it is not a valid tree
- for (int i = 0; i < n; i++) {
- if (colors[i] != 2) {
- return false;
- }
- }
- // graph is connected and has no cycle, it's a tree
- return true;
- }
- boolean hasCycleDfs(int at) {
- if (colors[at] != 0) {
- return colors[at] == 2;
- }
- colors[at] = 1;
- for (int to : graph.get(at)) {
- if (hasCycleDfs(to)) {
- return true;
- }
- }
- colors[at] = 2;
- return false;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement