作者：小迅

链接：https://leetcode.cn/problems/binary-tree-coloring-game/solutions/2090046/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-ukbyf/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目

示例

思路

题意 -> 给定一个二叉树，寻找两个起始点进行染色，谁染的多谁赢，题目给定已经存在了一个 x起始位置，我们需要寻找是否存在一个可以赢的y起始位置

题目说的挺有深度的，初开还以为需要将所有位置的一次，其实不用

对于任意一个 x 起始位置，他的下一步只可能存在三个位置：

• 父节点

• 左子节点

• 右子节点

那么我们 起始的 y 就只可能在这三个位置之上，因为只有这样才能让 x 的下一步所选择的位置更少 (局部最优)，x选择的位置变少了，那么我们y的位置就变多了，那么整体y的染色位置就多了(整体最优)。相当于 x 有三条路，我们选择 y 位置的时候，肯定是直接选择其中一条路的开始，而不会选择路的中间。

那么现在就是怎么选择这个三条路最优：

我们可以需要先找到 x 的位置在什么地方，然后统计一下 x 的 左子节点存在多少个子节点，右子节点存在多少个子节点，那么父节点就可以用 所有的节点 - 所有的左子节点 - 所有的右子节点 - 当前自己节点，那么现在所有路的节点我们都知道了，但是我们只能选择一条路堵死(可以自己想一下)，所以我们选择路上节点最多的路堵死，然后判断当前路上的节点是否比所有节点的一半多一个

代码注释超级详细

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* find_x(struct TreeNode *root, int x)//层次遍历搜索x位置
{
    struct TreeNode *queue[101];//基本的层次遍历
    int left = 0, right = 0;
    queue[right++] = root;
    while (left < right) {
        int r = right;
        while (left < r) {
            if (queue[left]->val == x) {
                return queue[left];
            }
            if (queue[left]->left != NULL) {
                queue[right++] = queue[left]->left;
            }
            if (queue[left]->right != NULL) {
                queue[right++] = queue[left]->right;
            }
            left++;
        }
    }
    return NULL;
} 

int dfs(struct TreeNode *root) //求对应子树的节点个数
{
    if (root == NULL) {
        return 0;
    }
    return 1 + dfs(root->left) + dfs(root->right);
}

bool btreeGameWinningMove(struct TreeNode* root, int n, int x){
    int leftnode = 0, rightnode = 0;
    struct TreeNode *node = find_x(root, x);//寻找x节点
    int left = dfs(node->left);
    int right = dfs(node->right);//求左右子树节点个数
    int m = n - left - right - 1;//求父节点个数
    int max = (left > right ? left : right);//取左右子节点最大值
    //其中有一个大于所有节点的一半+1则存在y点可以赢
    if (m > n / 2 || max > n / 2) {
        return true;
    }
    return false;
}

作者：小迅
链接：https://leetcode.cn/problems/binary-tree-coloring-game/solutions/2090046/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-ukbyf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。