JAVA DFS
\nThe first step is to find the node with value x. \nThe node will split whole tree into at almost three subtrees. \n \n   node x \'s left subtree, \n   node x\
\nThe first step is to find the node with value x. \nThe node will split whole tree into at almost three subtrees. \n ```\n   node x \'s left subtree, \n   node x\' s right subtree, \n   the rest of subtree from node\'x parent \n```\n \n If parent of node x is null, which means the node x is root node.  At this scenario, we only need to check if number of left subtree and number of right subtree are equal.  Because we assume players are very intelligent , and they will always try with bigger tree, then block this tree.\n \n If parent exists,   there are three subtrees. the second player will win if there is a tree whose number of nodes are larger than sum of number of nodes of rest two tree trees.\n \n ` \n int sum = parentNumber + leftNumber + rightNumber;\n  int max = Math.max(parentNumber, Math.max(leftNumber, rightNumber));\n  return max > sum - max;\t\t\n`\n\nBecause we need to know the amount of each subtree, so I will use a \n```\nMap<TreeNode, Integer> counts \n```\nto store number of children of each node during DFS process.\n\n```\npublic boolean btreeGameWinningMove(TreeNode root, int n, int x) {\n        Map<TreeNode, Integer> counts = new HashMap<TreeNode, Integer>();\n        TreeNode node = dfs(root, x, counts);\n        if (node == null) {\n            return false;\n        }\n        int parentNumber = n - counts.get(node);\n        int leftNumber =  node.left == null ? 0 : counts.get(node.left);\n        int rightNumber = node.right == null ? 0: counts.get(node.right);\n        int sum = parentNumber + leftNumber + rightNumber;\n        int max = Math.max(parentNumber, Math.max(leftNumber, rightNumber));\n        return max > sum - max;\n\n    }\n    \n    private TreeNode dfs(TreeNode root, int n, Map<TreeNode, Integer> counts) {\n        if (root == null) {\n            return null;\n        }\n        int sum = 1;\n        TreeNode left = dfs(root.left, n, counts);\n        TreeNode right = dfs(root.right, n, counts);\n        if (root.left != null) {\n            sum += counts.getOrDefault(root.left, 0);\n        }\n        \n        if (root.right != null) {\n            sum += counts.getOrDefault(root.right, 0);\n        }\n        \n        counts.put(root, sum);\n        if (left != null) {\n            return left;\n        } else if (right != null) {\n            return right;\n        } else if (root.val == n) {\n            return root;\n        } else {\n            return null;\n        }\n    }\n```\n\n
['Depth-First Search']