问题描述 链接到标题
解题思路 链接到标题
贪心策略：对二号玩家来说，想要取胜，选择染色节点只有三种可能：
- 选择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;
}
};