1145. Binary tree shader game

The title

Two geek players took part in a game called binary tree coloring. In the game, the root node of the binary tree root is given. There are a total of N nodes in the tree, and n is an odd number. The values on each node are different from 1 to n.

 

The game starts with player # 1 (player # 1 is red, player # 2 is blue), and at the very beginning,

Player # 1 takes a value x from [1, n] (1 <= x <= n);

Player 2 also takes a value y from [1, n] (1 <= y <= n) and y! = x.

Player # 1 colors nodes with value X in red, while player # 2 colors nodes with value Y in blue.

 

The two players then take turns, and each turn, the player chooses a node that he has previously colored, and colors an uncolored neighbor (left and right child nodes, or parent nodes) of the selected node.

If the current player cannot find such a node to dye, his turn is skipped.

If neither player has a node to dye, the game ends. The player with the most colored nodes wins ✌️.

 

Now, assuming you are player number two, return true if there is a value of y that guarantees you win the game based on the input given; If you cannot win, return false.

The sample

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3 output: TrueCopy the code

prompt

  • The root of the binary tree isrootThe tree bynThe value on the node ranges from1 到 nThey’re all different.
  • nFor an odd number.
  • 1 <= x <= n <= 100

Answer key

X has taken the first step; Y needs to have more dye nodes than X to win; That’s more than half the number of nodes n;

How do I get the most y stains? One way to think about it, block x

The next step of X can be dyed in three directions of the left child node, right child node or parent node of X; Is it possible to calculate the number of nodes in these three directions? If any of these three directions are greater than n over 2; Y would be able to dye in this direction ahead of time, blocking x’s path and winning, right?

According to this idea; The first step is to find the node where X is located. The second step is to find the number of nodes in the three directions of the left child node, right child node and parent node of x node

Return the answer

Edit the code as follows:

The complete code

var btreeGameWinningMove = function(root, n, x) {
    const current = findNode(root,x)
    const leftNodeNum = getNodeNum(current.left)
    const rightNodeNum = getNodeNum(current.right)
    const hlaf = n/2;
    const diff = n - leftNodeNum - rightNodeNum - 1;
    if(leftNodeNum > hlaf || rightNodeNum > hlaf || diff > hlaf  ) return true;
    return false


    function findNode(node,x){
        if(node === null) return null;
        if(node.val === x) return node;
        const left = findNode(node.left,x)
        const right = findNode(node.right,x)
        returnleft ! = =null ? left : right
    }

    function getNodeNum (node){
        if(node === null) return 0;
        return getNodeNum(node.left) + getNodeNum(node.right) + 1}};Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section