<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>

#include<vector> 
#include<math.h>  

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public: 
    std::unordered_set<int> visited ;  
    std::vector<std::vector<int>> graph ;  
    void insert(TreeNode* begin){
        std::queue<std::vector< TreeNode*>> nodes ;  
        nodes.push({begin,begin}) ; 
        while(nodes.size()>0){
            std::vector<TreeNode*> phase = nodes.front() ; 
            nodes.pop() ; 
            if (phase[0]==NULL){continue ;  } 
            std::vector<int>& prevs =  graph[phase[0]->val] ;  
            prevs[0] = phase[1]->val ;  
             if(phase[0]->left!=NULL){
                  prevs[1] = phase[0]->left->val ; 
                nodes.push({phase[0]->left,phase[0]}) ;   }  
            if(phase[0]->right!=NULL){
                prevs[2] = phase[0]->right->val ;  
                nodes.push({phase[0]->right,phase[0]}) ;   } 
        } 
    }  
    int traverse(int start ){  
        if(visited.find(start)!=visited.end()){return  0 ; } 
        visited.insert(start) ;
        std::queue<int> nodes  ; 
        nodes.push(start) ;
        int lapse = 0 ; 
        while(nodes.size()>0){
            const int phase = nodes.front() ; 
            nodes.pop() ; 
              lapse =lapse+1 ;  
            const std::vector<int>& nexts = graph[phase] ; 
            for(int ce=0;ce<nexts.size ();ce++ ){
                const int& temps = nexts[ce] ; 
                if(temps==0){continue ;}  
                if(visited.find(temps)!=visited.end()){continue ; } 
                visited.insert(temps) ; 
                nodes.push(temps) ; 
            }
        }  
        return lapse ;  
    }
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {  
        int range = n ;  
        visited = std::unordered_set<int>() ; 
         graph = std::vector<std::vector<int>>(range+1) ; 
        for(int fc=range;fc>=1;fc--){
            graph[fc]  =std::vector<int>(3) ; 
             for(int am=0;am<3;am++){
                graph[fc][am ] =  0  ; 
             } 
        }  
        insert(root) ; 
        const std::vector<int>& prevs = graph[x] ;  
        int greatest = 0 ;   
        visited.insert(x)  ;  
        int halfs =  (n+n%2)/2 ;   
        for(int cf=0;cf<prevs.size();cf++){
             int digit = prevs[cf] ; 
           //  std::cout<<digit ;  
             if(digit==0){continue ; }  
            int value = traverse(digit) ;   
            greatest = fmax(value,greatest) ; 
          //  std::cout<<value<<" " ;  
          //  if(value>=halfs){return true ; }
        }  
        if(greatest>=halfs){return true ;  }
        return false ; 
    }
};
14400