1145.二叉树着色游戏

问题描述

1145.二叉树着色游戏

解题思路

贪心策略：对二号玩家来说，想要取胜，选择染色节点只有三种可能：

• 选择x的父节点，则通过深度优先搜索可以求得红色节点数，蓝色节点数为$n$减去红色节点数
• 选择x的左子节点，则通过dfs可以求得蓝色节点数，红色节点数为$n$减去蓝色节点数
• 选择x的右子节点

代码

class Solution {
  public:
    int get_num(TreeNode *root) { // 获取当前树的节点数
        if (root != nullptr)
            return get_num(root->left) + get_num(root->right) + 1;
        else
            return 0;
    }
    TreeNode *get_pos(int x, int n, TreeNode *root) { // 获取当前x对应的指针
        if (root == nullptr)
            return nullptr;
        else {
            if (root->val == x)
                return root;
            else {
                TreeNode *l = get_pos(x, n, root->left);
                TreeNode *r = get_pos(x, n, root->right);
                if (l != nullptr)
                    return l;
                else
                    return r;
            }
        }
    }
    bool btreeGameWinningMove(TreeNode *root, int n, int x) {
        // 先判断是不是完全树
        if (n == 1)
            return false;
        TreeNode *nodex = get_pos(x, n, root);
        int num_blue1 = n - get_num(nodex); // 表示占据父节点
        int num_blue2 = get_num(nodex->left);
        int num_blue3 = get_num(nodex->right);
        if (num_blue1 > n - num_blue1)
            return true;
        if (num_blue2 > n - num_blue2)
            return true;
        if (num_blue3 > n - num_blue3)
            return true;
        return false;
    }
};