Advertisement
Guest User

Grokking Newsletter 240

a guest
Nov 10th, 2022
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.65 KB | Source Code | 0 0
  1. class Solution {
  2.    List<List<Integer>> graph;
  3.    int[] colors;
  4.    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
  5.        graph = new ArrayList<>();
  6.        colors = new int[n];
  7.        int[] numParents = new int[n];
  8.  
  9.        // build graph
  10.        for (int i = 0; i < n; i++) {
  11.            graph.add(new ArrayList<>());
  12.        }
  13.        for (int i = 0; i < n; i++) {
  14.            if (leftChild[i] != -1) {
  15.                graph.get(i).add(leftChild[i]);
  16.                graph.get(leftChild[i]).add(i);
  17.                numParents[leftChild[i]]++;
  18.            }
  19.            if (rightChild[i] != -1) {
  20.                graph.get(i).add(rightChild[i]);
  21.                graph.get(rightChild[i]).add(i);
  22.                numParents[rightChild[i]]++;
  23.            }
  24.        }
  25.  
  26.        // if there is a node with multiple parents, this is not a valid tree
  27.        for (int i = 0; i < n; i++) {
  28.            if (numParents[i] > 1) {
  29.                return false;
  30.            }
  31.        }
  32.  
  33.        // check cycle
  34.        hasCycleDfs(0);
  35.  
  36.        // there is unvisited node, the graph is not connected, it is not a valid tree
  37.        for (int i = 0; i < n; i++) {
  38.            if (colors[i] != 2) {
  39.                return false;
  40.            }
  41.        }
  42.  
  43.        // graph is connected and has no cycle, it's a tree
  44.        return true;
  45.    }
  46.  
  47.    boolean hasCycleDfs(int at) {
  48.        if (colors[at] != 0) {
  49.            return colors[at] == 2;
  50.        }
  51.  
  52.        colors[at] = 1;
  53.        for (int to : graph.get(at)) {
  54.            if (hasCycleDfs(to)) {
  55.                return true;
  56.            }
  57.        }
  58.  
  59.        colors[at] = 2;
  60.  
  61.        return false;
  62.    }
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement