Code & Func

第50天。

挺唬人的题目，搞清楚题意的话，还是挺简单的。

大概的意思是，现在有一个树，然后已经有个人将其中一个节点上色成红色，问你，现在按顺序涂颜色，最后你能不能赢。这个的规则有两个：

除了第一个颜色可以随便找节点上色外，其他的都只能对自己临近的节点上色。
有颜色的节点不能再次上色
所以节点上完色后，节点多的人获胜

因为是在树上，所以给第二个以及之后的节点上色的话，只有三种选择，向父节点、向左节点、向右节点。

所以我们只要判断对手上色的第一个节点，三个方向中，是否存在一个方向的节点比剩余节点都要多。

1
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
2
    if (!root) return false;
3
    TreeNode *node = search(root, x);
4

5
    int leftNum = getNodeNum(node->left);
6
    int rightNum = getNodeNum(node->right);
7
    int upNum = n - 1 - leftNum - rightNum;
8
    int maxNum = max(max(leftNum, rightNum), upNum);
9
    // cout << leftNum << endl;
10
    // cout << rightNum << endl;
11
    // cout << upNum << endl;
12
    // cout << maxNum << endl;
13
    return maxNum > (n - maxNum);
14

15
}
12 collapsed lines
16

17
int getNodeNum(TreeNode *root) {
18
    if (!root) return 0;
19
    return 1 + getNodeNum(root->left) + getNodeNum(root->right);
20
}
21

22
TreeNode *search(TreeNode *root, int x) {
23
    if (!root || root->val == x) return root;
24
    TreeNode *node = search(root->left, x);
25
    if (node) return node;
26
    return search(root->right, x);
27
}