Leetcode 1145: Binary Tree Coloring Game
Two players play a turn-based game on a binary tree. We are given the root of the tree and the number of nodes,
n, where n is odd, and each node has a distinct value from 1 to n. Player 1 selects a value x and colors the corresponding node red, while Player 2 selects a value y (where y ≠ x) and colors the corresponding node blue. Players take turns coloring neighboring nodes. The game ends when both players pass their turns, and the winner is the player who colored more nodes. Your task is to determine if Player 2 can guarantee a win by choosing a value y.Problem
Approach
Steps
Complexity
Input: The input consists of the root of the binary tree, an integer `n` representing the total number of nodes, and an integer `x` representing the value Player 1 selects.
Example: Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Constraints:
• 1 <= x <= n <= 100
• n is odd
• 1 <= Node.val <= n
• All the values of the tree are unique
Output: Return true if Player 2 can guarantee a win by choosing a value `y`, otherwise return false.
Example: Output: true
Constraints:
• The output should be a boolean value.
Goal: The goal is to determine if Player 2 can guarantee a win by choosing the right value `y`.
Steps:
• 1. Traverse the tree and count the number of nodes in the left and right subtrees of the node where Player 1 colors the node.
• 2. Calculate the maximum number of nodes Player 2 can color by strategically choosing the correct starting node `y`.
• 3. Return true if Player 2 can color more nodes than Player 1; otherwise, return false.
Goal: The solution should be efficient for a tree with up to 100 nodes.
Steps:
• 1 <= n <= 100
• n is odd
• 1 <= Node.val <= n
• All values are unique
Assumptions:
• The tree is a valid binary tree with no missing nodes.
• Player 1 always starts the game by selecting a node `x`.
• Input: Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
• Explanation: In this case, Player 2 can select the node with value 2, which allows them to guarantee a win.
• Input: Input: root = [1,2,3], n = 3, x = 1
• Explanation: In this case, Player 1 can always win no matter what node Player 2 selects.
Approach: To solve this problem, we can use a depth-first search (DFS) to calculate the number of nodes in the left and right subtrees of the node where Player 1 colors a node. The key idea is to ensure Player 2 can color more nodes by strategically choosing the starting node `y`.
Observations:
• We need to track the number of nodes in the left and right subtrees of Player 1's node to calculate the optimal strategy for Player 2.
• A DFS approach can help us calculate the size of subtrees and determine the best node for Player 2 to start the game.
Steps:
• 1. Traverse the tree and count the nodes in the left and right subtrees of the node where Player 1 colors a node.
• 2. Use this information to calculate the maximum number of nodes Player 2 can color by selecting an appropriate node `y`.
• 3. If Player 2 can color more nodes than Player 1, return true; otherwise, return false.
Empty Inputs:
• If the tree has no nodes, the game cannot be played.
Large Inputs:
• For large trees with up to 100 nodes, the solution should still be efficient.
Special Values:
• If `x` is the root node, Player 2 must select a neighboring node to start.
Constraints:
• The tree is always a valid binary tree with distinct node values.
int lft, rht, val;
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
val = x;
cout<< n;
n = count(root);
cout<< n << "\n";
return max(max(lft, rht), n - lft-rht -1) > n/2;
}
int count(TreeNode* root) {
if(!root) return 0;
int l = count(root->left);
int r = count(root->right);
if(root->val == val)
lft = l, rht = r;
return l + r + 1;
}
};
1 : Variable Declaration
int lft, rht, val;
The variables `lft`, `rht`, and `val` are declared. `lft` and `rht` will store the sizes of the left and right subtrees of the node `x`, while `val` stores the value of the node `x` for comparison in the recursive function.
2 : Function Definition
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
The function `btreeGameWinningMove` is defined, which takes the root of the binary tree, the total number of nodes (`n`), and the value `x` of the target node to determine if the game can be won.
3 : Value Assignment
val = x;
The value of `x` (the target node) is assigned to the `val` variable. This allows the program to identify the subtree rooted at node `x` during the recursion.
4 : Subtree Size Calculation
n = count(root);
The function `count` is called with the root of the tree to calculate the size of the entire tree. This value is reassigned to `n`.
5 : Decision Making
return max(max(lft, rht), n - lft - rht - 1) > n / 2;
This line calculates the largest possible subtree that can be isolated after a move, comparing the sizes of the left, right, and the remaining nodes. If the size of the largest subtree is greater than half the total tree size, it returns `true`, indicating a winning move.
6 : Helper Function Definition
int count(TreeNode* root) {
The helper function `count` is defined, which recursively calculates the size of the subtree rooted at `root`. It also checks whether the node matches the target node `x`.
7 : Base Case
if(!root) return 0;
This is the base case of the recursion. If the `root` is null, it returns 0, indicating that there are no nodes in this subtree.
8 : Recursive Calls
int l = count(root->left);
This recursively calls the `count` function on the left child of the current node to calculate the size of the left subtree.
9 : Recursive Calls
int r = count(root->right);
This recursively calls the `count` function on the right child of the current node to calculate the size of the right subtree.
10 : Target Node Check
if(root->val == val)
This checks if the current node is the target node `x` (whose value is stored in `val`). If true, the sizes of the left and right subtrees are stored in `lft` and `rht` respectively.
11 : Subtree Size Assignment
lft = l, rht = r;
The sizes of the left and right subtrees are assigned to the variables `lft` and `rht` when the target node is found.
12 : Return Statement
return l + r + 1;
This returns the size of the current subtree by summing the sizes of the left and right subtrees, and adding 1 for the current node.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we visit each node in the tree once.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the recursive call stack in the depth-first search.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus