LeetCode - 1145. Binary Tree Coloring Game

链接：https://leetcode-cn.com/problems/binary-tree-coloring-game/
难度：medium

解题思路：将二叉树以玩家1选择的节点为基准分为三部分，他的父亲部分，他的左孩子部分，右孩子部分。玩家二只有可能占据其中一部分，而只要其中一部分超过一半节点就可以获胜，所以解题思路转换为计算二叉树的这三部分，利用深搜来解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int left = 0;
    int right = 0;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int parent = dfs(root, x);
        int count = n / 2;
        return parent > count || left > count || right > count;
    }

    private int dfs(TreeNode node, int x) {
        if (node == null) {
            return 0;
        }
        if(node.val == x) {
            // 找到目标节点后统计其左右孩子的数量
            if(node.left != null) {
                this.left = dfs(node.left, -1) + 1;
            }
            if(node.right != null) {
                this.right = dfs(node.right, -1) + 1;
            }
            return 0;
        }
        int count = 0;
        if(node.left != null) {
            count += dfs(node.left, x) + 1;
        }
        if(node.right != null) {
            count += dfs(node.right, x) + 1;
        }
        return count;
    }
}