package leetcode;

/**
 * https://leetcode.com/problems/validate-binary-tree-nodes/
 */
public class Problem1361 {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] inCount = new int[n];
        int[] outCount = new int[n];
        for (int i = 0; i < n; i++) {
            // there should not be any edge going into the root
            if (leftChild[i] == 0 || rightChild[i] == 0) {
                return false;
            }
            if (leftChild[i] > 0) {
                outCount[i]++;
                inCount[leftChild[i]]++;
                if (inCount[leftChild[i]] > 1) {
                    return false;
                }
            }
            if (rightChild[i] > 0) {
                outCount[i]++;
                inCount[rightChild[i]]++;
                if (inCount[rightChild[i]] > 1) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem1361 prob = new Problem1361();
//        System.out.println(prob.validateBinaryTreeNodes(4, new int[]{1,-1,3,-1}, new int[]{2,-1,-1,-1})); // true
//        System.out.println(prob.validateBinaryTreeNodes(4, new int[]{1,-1,3,-1}, new int[]{2,3,-1,-1})); // false
//        System.out.println(prob.validateBinaryTreeNodes(2, new int[]{1,0}, new int[]{-1,-1})); // false
//        System.out.println(prob.validateBinaryTreeNodes(3, new int[]{1,2,1}, new int[]{-1,-1,-1})); // false
        System.out.println(prob.validateBinaryTreeNodes(6, new int[]{1,-1,-1,4,-1,-1}, new int[]{2,-1,-1,5,-1,-1})); // false
//        System.out.println(prob.validateBinaryTreeNodes(5, new int[]{3,-1,-1,1,-1}, new int[]{4,-1,-1,2,-1})); // true
    }
}

@@ -321,17 +321,17 @@
      // 
-t
+T
 here sho
@@ -369,16 +369,17 @@
 the root
+.
 %0A       
@@ -945,567 +945,186 @@
     
-return true;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1361 prob = new Problem1361();%0A//        System.out.println(prob.validateBinaryTreeNodes(4, new int%5B%5D%7B1,-1,3,-1%7D, new int%5B%5D%7B2,-1,-1,-1%7D)); // true%0A//        System.out.println(prob.validateBinaryTreeNodes(4, new int%5B%5D%7B1,-1,3,-1%7D, new int%5B%5D%7B2,3,-1,-1%7D)); // false%0A//        System.out.println(prob.validateBinaryTreeNodes(2, new int%5B%5D%7B1,0%7D, new int%5B%5D%7B-1,-1%7D)); // false%0A//        System.out.println(prob.validateBinaryTreeNodes(3, new int%5B%5D%7B1,2,1%7D, new int%5B%5D%7B-1,-1,-1%7D)); //
+// Other than root, there should be exactly one edge going into every node.%0A        for (int i = 1; i %3C n; i++) %7B%0A            if (inCount%5Bi%5D != 1) %7B%0A                return
  false
+;
 %0A   
@@ -1132,246 +1132,44 @@
     
-System.out.println(prob.validateBinaryTreeNodes(6, new int%5B%5D%7B1,-1,-1,4,-1,-1%7D, new int%5B%5D%7B2,-1,-1,5,-1,-1%7D)); // false%0A//        System.out.println(prob.validateBinaryTreeNodes(5, new int%5B%5D%7B3,-1,-1,1,-1%7D, new int%5B%5D%7B4,-1,-1,2,-1%7D)); //
+    %7D%0A        %7D%0A        return
  true
+;
 %0A   

Solve problem 1361