package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/binary-tree-coloring-game/
 */
public class Problem1145 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int[] counts = new int[n + 1];
        getChildCount(root, counts);
        System.out.println(Arrays.toString(counts));
        List<Integer> adjacents = new ArrayList<>();
        getAdjacents(null, root, x, adjacents);
        System.out.println(adjacents);
        return false;
    }

    private static void getAdjacents(TreeNode parent, TreeNode current,
                                     int x, List<Integer> adjacents) {
        if (current == null) {
            return;
        }
        if (current.val == x) {
            if (parent != null) {
                adjacents.add(parent.val);
            }
            if (current.left != null) {
                adjacents.add(current.left.val);
            }
            if (current.right != null) {
                adjacents.add(current.right.val);
            }
            return;
        }
        getAdjacents(current, current.left, x, adjacents);
        getAdjacents(current, current.right, x, adjacents);
    }

    private static int getChildCount(TreeNode root, int[] counts) {
        if (root == null) {
            return 0;
        }
        int count = getChildCount(root.left, counts) + getChildCount(root.right, counts) + 1;
        counts[root.val] = count;
        return count;
    }

    public static void main(String[] args) {
        Problem1145 prob = new Problem1145();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);

        System.out.println(prob.btreeGameWinningMove(root, 11, 3)); // true
//        System.out.println(prob.btreeGameWinningMove(root, 11, 2)); // false
//        System.out.println(prob.btreeGameWinningMove(root, 11, 1)); // true
    }
}

@@ -29,25 +29,23 @@
 va.util.
-ArrayList
+HashMap
 ;%0Aimport
@@ -59,37 +59,11 @@
 til.
-Arrays;%0Aimport java.util.List
+Map
 ;%0A%0A/
@@ -479,51 +479,189 @@
     
-System.out.println(Arrays.toString(
+Map%3CType, Integer%3E adjacents = new HashMap%3C%3E();%0A        getAdjacents(null, root, x, adjacents);%0A        if (adjacents.get(Type.PARENT) != null) %7B%0A            int player1 = 
 counts
-))
+%5Bx%5D
 ;%0A  
@@ -670,161 +670,786 @@
     
-List%3CInteger%3E adjacents = new ArrayList%3C%3E();%0A        getAdjacents(null, root, x, adjacents);%0A        System.out.println(adjacents);%0A        return false;
+    int player2 = n - counts%5Bx%5D;%0A            if (player1 %3C player2) %7B%0A                return true;%0A            %7D%0A        %7D%0A        if (adjacents.get(Type.LEFT_CHILD) != null) %7B%0A            int player1 = n - counts%5Badjacents.get(Type.LEFT_CHILD)%5D;%0A            int player2 = counts%5Badjacents.get(Type.LEFT_CHILD)%5D;%0A            if (player1 %3C player2) %7B%0A                return true;%0A            %7D%0A        %7D%0A        if (adjacents.get(Type.RIGHT_CHILD) != null) %7B%0A            int player1 = n - counts%5Badjacents.get(Type.RIGHT_CHILD)%5D;%0A            int player2 = counts%5Badjacents.get(Type.RIGHT_CHILD)%5D;%0A            if (player1 %3C player2) %7B%0A                return true;%0A            %7D%0A        %7D%0A        return false;%0A    %7D%0A%0A    private enum Type %7B%0A        PARENT, LEFT_CHILD, RIGHT_CHILD
 %0A   
@@ -1572,13 +1572,18 @@
  x, 
-List%3C
+Map%3CType, 
 Inte
@@ -1753,20 +1753,33 @@
 jacents.
-add(
+put(Type.PARENT, 
 parent.v
@@ -1855,36 +1855,53 @@
       adjacents.
-add(
+put(Type.LEFT_CHILD, 
 current.left.val
@@ -1988,12 +1988,30 @@
 nts.
-add(
+put(Type.RIGHT_CHILD, 
 curr
@@ -2483,822 +2483,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1145 prob = new Problem1145();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.right = new TreeNode(3);%0A        root.left.left = new TreeNode(4);%0A        root.left.right = new TreeNode(5);%0A        root.right.left = new TreeNode(6);%0A        root.right.right = new TreeNode(7);%0A        root.left.left.left = new TreeNode(8);%0A        root.left.left.right = new TreeNode(9);%0A        root.left.right.left = new TreeNode(10);%0A        root.left.right.right = new TreeNode(11);%0A%0A        System.out.println(prob.btreeGameWinningMove(root, 11, 3)); // true%0A//        System.out.println(prob.btreeGameWinningMove(root, 11, 2)); // false%0A//        System.out.println(prob.btreeGameWinningMove(root, 11, 1)); // true%0A    %7D
 %0A%7D%0A

Solve problem 1145