Description Link to heading
1145.binary-tree-coloring-game
Solution Link to heading
Greedy algorithm: for second player, if he wants to win, there are three ways to color the node.
- color the parent node of
x, then we use dfs to get the number of red nodes, the number of blue nodes is $n$ minus the nubmer of red nodes; - color the left child node of
x, then we use dfs to get the number of blue nodes, the number of red nodes is $n$ minus the number of blue nodes; - color the right child node of
x
Code Link to heading
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;
}
};