You are given the root
of a binary tree with the following properties:
- Leaf nodes have either the value
0
or1
, representingfalse
andtrue
respectively. - Non-leaf nodes have either the value
2
,3
,4
, or5
, representing the boolean operationsOR
,AND
,XOR
, andNOT
, respectively.
You are also given a boolean result
, which is the desired result of the evaluation of the root
node.
The evaluation of a node is as follows:
- If the node is a leaf node, the evaluation is the value of the node, i.e.
true
orfalse
. - Otherwise, evaluate the node's children and apply the boolean operation of its value with the children's evaluations.
In one operation, you can flip a leaf node, which causes a false
node to become true
, and a true
node to become false
.
Return the minimum number of operations that need to be performed such that the evaluation of root
yields result
. It can be shown that there is always a way to achieve result
.
A leaf node is a node that has zero children.
Note: NOT
nodes have either a left child or a right child, but other non-leaf nodes have both a left child and a right child.
Example 1:
Input: root = [3,5,4,2,null,1,1,1,0], result = true Output: 2 Explanation: It can be shown that a minimum of 2 nodes have to be flipped to make the root of the tree evaluate to true. One way to achieve this is shown in the diagram above.
Example 2:
Input: root = [0], result = false Output: 0 Explanation: The root of the tree already evaluates to false, so 0 nodes have to be flipped.
Constraints:
- The number of nodes in the tree is in the range
[1, 105]
. 0 <= Node.val <= 5
OR
,AND
, andXOR
nodes have2
children.NOT
nodes have1
child.- Leaf nodes have a value of
0
or1
. - Non-leaf nodes have a value of
2
,3
,4
, or5
.
Companies: Google
Related Topics:
Dynamic Programming, Tree, Depth-First Search, Binary Tree
Similar Questions:
- Check If Two Expression Trees are Equivalent (Medium)
- Design an Expression Tree With Evaluate Function (Medium)
- Evaluate Boolean Binary Tree (Easy)
Hints:
- Try using tree DP to solve this problem.
- Find the minimum operations to change each subtree to true and to false separately.
- For nodes representing boolean operations, find the minimum operations by trying all combinations of values to which the child nodes can evaluate.
// OJ: https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
unordered_map<TreeNode*, int> m[2];
public:
int minimumFlips(TreeNode* root, bool result) {
if (!root->left && !root->right) return result != root->val;
if (m[result].count(root)) return m[result][root];
int ans;
if (root->val == 2) { // OR
if (result) ans = min(minimumFlips(root->left, true), minimumFlips(root->right, true));
else ans = minimumFlips(root->left, false) + minimumFlips(root->right, false);
} else if (root->val == 3) { // AND
if (result) ans = minimumFlips(root->left, true) + minimumFlips(root->right, true);
else ans = min(minimumFlips(root->left, false), minimumFlips(root->right, false));
} else if (root->val == 4) { // XOR
if (result) ans = min(minimumFlips(root->left, true) + minimumFlips(root->right, false), minimumFlips(root->left, false) + minimumFlips(root->right, true));
else ans = min(minimumFlips(root->left, true) + minimumFlips(root->right, true), minimumFlips(root->left, false) + minimumFlips(root->right, false));
} else { // NOT
auto node = root->left ? root->left : root->right;
ans = minimumFlips(node, !result);
}
return m[result][root] = ans;
}
};
// OJ: https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
array<int, 2> dfs(TreeNode *root) { // minimum operations to get result `false` / `true`.
if (!root) return {INT_MAX, INT_MAX};
if (root->val <= 1) return {root->val, !root->val};
auto [a, b] = dfs(root->left);
auto [c, d] = dfs(root->right);
if (root->val == 2) { // OR
return {a + c, min(b, d)};
} else if (root->val == 3) { // AND
return {min(a, c), b + d};
} else if (root->val == 4) { // XOR
return {min(a + c, b + d), min(a + d, b + c)};
} else { // NOT
return {min(b, d), min(a, c)};
}
}
public:
int minimumFlips(TreeNode* root, bool result) {
return dfs(root)[result];
}
};