Leetcode 1145: Binary Tree Coloring Game

https://leetcode.com/problems/binary-tree-coloring-game/description/

Notes:

The description above is not clear actually. Basically it says two players A and B will play alternatively and optimally. A pick up X first, then it will be B's turn to pick up any one of the remaining nodes. After that, it backs to A's turn to pick one.

Now A cannot choose any one he likes: he has to choose a): it is not picked (colored) yet; b): it must be the neighbor of his previously picks (or the same color). It can be either the left-kid, right-kid, or the parent. After that, it is B's turn and B follows the same rule.

The key observation is that: After the A player pick up x, then B player need to choose maximum of three cases: the left-kid subtree, right-kid subtree, or on the x parent side. If B always play optimally, B will choose the maximum of the three cases.

Then B will color or pick all the nodes in that subtree, since A cannot cross over. Similarly, B cannot cross over to the rest part of the tree. And all the rest nodes will be picked or colored by A.

If the maximum of three cases is larger than n/2, then B will win.

It is relative easier to calculate the number of nodes in the left-kid subtree and right-kid subtree than that on the parent side. However, we know the total is n, thus, when the left and right parts are calculated, then the rest part will be (n - left - right - 1).

See the code below:

/*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        int lt = 0, rt = 0;
        dsf(root, lt, rt, x);
        return max(max(lt, rt), n-lt-rt-1) > n/2;
    }
private:
    int dsf(TreeNode* r, int &lt, int &rt, int &x) {
        if(!r) return 0;
        int left = dsf(r->left, lt, rt, x), right = dsf(r->right, lt, rt, x);
        if(r->val == x) {
            lt = left;
            rt = right;
        }
        return left + right + 1;
    }
};

The follow up question:

Let say A will pick up first and can pick up any node he likes. Then the question is that: is there a node that A can pick up or color firstly to guarantee that he will win eventually? If yes, output all these nodes that can be chosen as the first node for A.

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        vector<int> vs;
        dsf(root, n, x, vs);
        return vs;
    }

private:
    int dsf(TreeNode* r, int &n, int &x, vector<int> &ns) {
        if(!r) return 0;
        int left = dsf(r->left, n, x, vs), right = dsf(r->right, n, x, vs);
        if(max(max(left, right), n-left-right-1)) <= n/2 ) vs.push_back(r->val);
        return left + right + 1;
    }
};