You are given a binary tree root representing a game state of a two person game. Every internal node is filled with an empty value of 0 while the leaves values represent the end score. You want to maximize the end score while your opponent wants to minimize the end score.
You will always make moves on nodes at even levels and your opponent will always make moves on odd levels. Fill in the binary tree with the resulting scores assuming both of you play optimally.
Constraints
n ≤ 100,000 where n is the number of nodes in rootHints:
Try using depth-first-search.
Take into account whether the current node is at odd level or even level.
MinMax Tree Game
MinMax Tree can be used in a game strategy search. One player tries to maximize the score and another tries to minimize the score. With pruning, it will become Alpha-Beta pruning algorithm.
We can use the Depth First Search Algorithm (DFS) to traverse the tree and passing down the level value. Then, for odd/even levels, we deal differently one maximizing and another minimizing.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ Tree* minmaxTree(Tree* root) { if (!root) return root; function<void(Tree*, int)> dfs = [&](Tree* root, int level) { if (!root) return; dfs(root->left, level + 1); dfs(root->right, level + 1); if ((level & 1) == 0) { int m = INT_MIN; if (root->left) m = max(m, root->left->val); if (root->right) m = max(m, root->right->val); root->val = m == INT_MIN ? root->val : m; } else { int m = INT_MAX; if (root->left) m = min(m, root->left->val); if (root->right) m = min(m, root->right->val); root->val = m == INT_MAX ? root->val : m; } }; dfs(root, 0); return root; } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
Tree* minmaxTree(Tree* root) {
if (!root) return root;
function<void(Tree*, int)> dfs = [&](Tree* root, int level) {
if (!root) return;
dfs(root->left, level + 1);
dfs(root->right, level + 1);
if ((level & 1) == 0) {
int m = INT_MIN;
if (root->left) m = max(m, root->left->val);
if (root->right) m = max(m, root->right->val);
root->val = m == INT_MIN ? root->val : m;
} else {
int m = INT_MAX;
if (root->left) m = min(m, root->left->val);
if (root->right) m = min(m, root->right->val);
root->val = m == INT_MAX ? root->val : m;
}
};
dfs(root, 0);
return root;
}A better/shorter DFS implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ int min_max_game(Tree* root, bool take_max) { if (!root) return take_max ? INT_MAX : INT_MIN; if (!root->left && !root->right) { return root->val; } int left = min_max_game(root->left, !take_max); int right = min_max_game(root->right, !take_max); root->val = take_max ? max(left, right) : min(left, right); return root->val; } Tree* minmaxTree(Tree* root) { min_max_game(root, true); return root; } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
int min_max_game(Tree* root, bool take_max) {
if (!root) return take_max ? INT_MAX : INT_MIN;
if (!root->left && !root->right) {
return root->val;
}
int left = min_max_game(root->left, !take_max);
int right = min_max_game(root->right, !take_max);
root->val = take_max ? max(left, right) : min(left, right);
return root->val;
}
Tree* minmaxTree(Tree* root) {
min_max_game(root, true);
return root;
}The time complexity is O(N) as we are traversing the nodes in the MinMax tree. The space complexity is O(H) where H is the height of the binary tree and in worst case H is equal to N for a highly de-generated tree – linked list.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Using Dynamic Programming to Count the Number of Palindrome Substrings
Next Post: Compute the Sliding Window Max using Monetone Decreasing Double-ended Queue
