Approach

For each node, recursively compute the minimum flips needed to make its subtree evaluate to True and False.
For leaf nodes, flips are needed only if their value does not match the target.
For non-leaf nodes, use the operation type to combine the results from children, considering all possible combinations and flips.
Use memoization to avoid recomputation.
Return the minimum flips needed for the root to achieve the desired result.

Code

[{"language":"C++","code":"struct TreeNode {\n    int val;\n    TreeNode *left, *right;\n};\n\nclass Solution {\nprivate:\n    unordered_map<TreeNode*, array<int,2>> dp;\n    \n    void dfs(TreeNode* node) {\n        if (!node) return;\n        \n        if (node->val == 0 || node->val == 1) {\n            dp[node][node->val] = 0;\n            dp[node][1-node->val] = 1;\n            return;\n        }\n        \n        if (dp.count(node)) return;\n        \n        // Process children first\n        if (node->left) dfs(node->left);\n        if (node->right) dfs(node->right);\n        \n        dp[node] = {1e9, 1e9};\n        \n        if (node->val == 2) { // OR\n            for (int a = 0; a < 2; ++a)\n                for (int b = 0; b < 2; ++b) {\n                    int res = a | b;\n                    dp[node][res] = min(dp[node][res], dp[node->left][a] + dp[node->right][b]);\n                }\n        } else if (node->val == 3) { // AND\n            for (int a = 0; a < 2; ++a)\n                for (int b = 0; b < 2; ++b) {\n                    int res = a & b;\n                    dp[node][res] = min(dp[node][res], dp[node->left][a] + dp[node->right][b]);\n                }\n        } else if (node->val == 4) { // XOR\n            for (int a = 0; a < 2; ++a)\n                for (int b = 0; b < 2; ++b) {\n                    int res = a ^ b;\n                    dp[node][res] = min(dp[node][res], dp[node->left][a] + dp[node->right][b]);\n                }\n        } else if (node->val == 5) { // NOT\n            TreeNode* child = node->left ? node->left : node->right;\n            for (int a = 0; a < 2; ++a) {\n                int res = 1 - a;\n                dp[node][res] = min(dp[node][res], dp[child][a]);\n            }\n        }\n    }\n    \npublic:\n    int minimumFlips(TreeNode* root, bool result) {\n        dfs(root);\n        return dp[root][result];\n    }\n};","lang":"cpp"},{"language":"Go","code":"type TreeNode struct {\n    Val   int\n    Left  *TreeNode\n    Right *TreeNode\n}\n\nfunc minimumFlips(root *TreeNode, result bool) int {\n    var dfs func(*TreeNode) [2]int\n    dfs = func(node *TreeNode) [2]int {\n        if node == nil {\n            return [2]int{0, 0}\n        }\n        \n        // Leaf nodes\n        if node.Val == 0 {\n            return [2]int{0, 1} // [false_cost, true_cost]\n        }\n        if node.Val == 1 {\n            return [2]int{1, 0} // [false_cost, true_cost]\n        }\n        \n        // Process children\n        var left, right [2]int\n        if node.Left != nil {\n            left = dfs(node.Left)\n        }\n        if node.Right != nil {\n            right = dfs(node.Right)\n        }\n        \n        dp := [2]int{1e9, 1e9}\n        \n        if node.Val == 2 { // OR\n            for a := 0; a < 2; a++ {\n                for b := 0; b < 2; b++ {\n                    res := a | b\n                    cost := left[a] + right[b]\n                    if cost < dp[res] {\n                        dp[res] = cost\n                    }\n                }\n            }\n        } else if node.Val == 3 { // AND\n            for a := 0; a < 2; a++ {\n                for b := 0; b < 2; b++ {\n                    res := a & b\n                    cost := left[a] + right[b]\n                    if cost < dp[res] {\n                        dp[res] = cost\n                    }\n                }\n            }

Related Tags