<p>Two players play a turn based game on a binary tree. We are given the <code>root</code> of this binary tree, and the number of nodes <code>n</code> in the tree. <code>n</code> is odd, and each node has a distinct value from <code>1</code> to <code>n</code>.</p>

<p>Initially, the first player names a value <code>x</code> with <code>1 &lt;= x &lt;= n</code>, and the second player names a value <code>y</code> with <code>1 &lt;= y &lt;= n</code> and <code>y != x</code>. The first player colors the node with value <code>x</code> red, and the second player colors the node with value <code>y</code> blue.</p>

<p>Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an <strong>uncolored</strong> neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)</p>

<p>If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.</p>

<p>You are the second player. If it is possible to choose such a <code>y</code> to ensure you win the game, return <code>true</code>. If it is not possible, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/01/1480-binary-tree-coloring-game.png" style="width: 500px; height: 310px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
<strong>Output:</strong> true
<strong>Explanation: </strong>The second player can choose the node with value 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [1,2,3], n = 3, x = 1
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>1 &lt;= x &lt;= n &lt;= 100</code></li>
	<li><code>n</code> is odd.</li>
	<li>1 &lt;= Node.val &lt;= n</li>
	<li>All the values of the tree are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    TreeNode *xNode;
    void fillParent(TreeNode * head, vector<TreeNode *> &p,int x){
        if(head != NULL){
            if(head->left){
                p[head->left->val]=head;
                fillParent(head->left,p,x);
            }
            if(head->right){
                p[head->right->val]=head;
                fillParent(head->right,p,x);
            }
            if(head->val == x) xNode = head;
        }
    }
    bool checkForY(TreeNode *y, vector<TreeNode *> &p, TreeNode *x,int n){
        vector<int> vis(n+1,0);
        vis[x->val]=1;
        vis[y->val]=2;

        queue<TreeNode *> q1;
        queue<TreeNode *> q2;
        q1.push(x);
        q2.push(y);

        int xcnt=0,ycnt=0;

        while(!q1.empty() || !q2.empty()){
            if(!q1.empty()){
                TreeNode * f = q1.front();
                q1.pop();
                xcnt++;
                if(p[f->val] && vis[p[f->val]->val]==0){
                    q1.push(p[f->val]);
                    vis[p[f->val]->val]=1;
                }
                if(f->left && vis[f->left->val]==0){
                    q1.push(f->left);
                    vis[f->left->val]=1;
                }
                if(f->right && vis[f->right->val]==0){
                    q1.push(f->right);
                    vis[f->right->val]=1;
                }
            }
            if(!q2.empty()){
                TreeNode * f = q2.front();
                q2.pop();
                ycnt++;
                if(p[f->val] && vis[p[f->val]->val]==0){
                    q2.push(p[f->val]);
                    vis[p[f->val]->val]=2;
                }
                if(f->left && vis[f->left->val]==0){
                    q2.push(f->left);
                    vis[f->left->val]=2;
                }
                if(f->right && vis[f->right->val]==0){
                    q2.push(f->right);
                    vis[f->right->val]=2;
                }
            }
        }
        return ycnt > xcnt;
    }
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        vector<TreeNode *> parent(n+1);
        TreeNode *head = root;
        fillParent(head,parent,x);

        bool  a1=false, a2 = false, a3 = false;
        if(root != xNode) a1 = checkForY(parent[xNode->val],parent,xNode,n);
        if(xNode->left) a2 = checkForY(xNode->left,parent,xNode,n);
        if(xNode->right) a3 = checkForY(xNode->right,parent,xNode,n);

        if(a1 || a2 || a3){
            return true;
        }
        return false;
    }
};
13700