2313 solved.

liuyubobobo · liuyubobobo · commit b3397d0c5710 · 2022-06-22T23:36:49.000-07:00
diff --git a/2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/CMakeLists.txt b/2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_2313)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_2313 main.cpp)
diff --git a/2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/main.cpp b/2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/main.cpp
@@ -0,0 +1,72 @@
+/// Source : https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result/
+/// Author : liuyubobobo
+/// Time   : 2022-06-22
+
+#include <iostream>
+#include <vector>
+#include <unordered_map>
+#include <cassert>
+
+using namespace std;
+
+
+/// Tree DP
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+/// Definition for a binary tree node.
+struct TreeNode {
+    int val;
+    TreeNode *left;
+    TreeNode *right;
+    TreeNode() : val(0), left(nullptr), right(nullptr) {}
+    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+};
+
+class Solution {
+public:
+    int minimumFlips(TreeNode* root, bool result) {
+
+        vector<unordered_map<TreeNode*, int>> dp(2);
+        return dfs(root, result, dp);
+    }
+
+private:
+    int dfs(TreeNode* node, bool result, vector<unordered_map<TreeNode*, int>>& dp){
+
+        if(node->left == nullptr && node->right == nullptr)
+            return result != node->val;
+
+        auto iter = dp[result].find(node);
+        if(iter != dp[result].end()) return iter->second;
+
+        if(node->val == 5){
+            TreeNode* child = node->left ? node->left : node->right;
+            return dp[result][node] = dfs(child, !result, dp);
+        }
+
+        TreeNode* node1 = node->left, *node2 = node->right;
+        int res = INT_MAX;
+        for(int res1 = 0; res1 <= 1; res1 ++)
+            for(int res2 = 0; res2 <= 1; res2 ++)
+                if(calc(res1, res2, node->val) == result)
+                    res = min(res, dfs(node1, res1, dp) + dfs(node2, res2, dp));
+        return dp[result][node] = res;
+    }
+
+    int calc(int a, int b, int op){
+        switch(op){
+            case 2: return a | b;
+            case 3: return a & b;
+            case 4: return a ^ b;
+            default: assert(false);
+        }
+        return -1;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2158,6 +2158,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2310 | [Sum of Numbers With Units Digit K](https://leetcode.com/problems/sum-of-numbers-with-units-digit-k/) | [无] | [C++](2001-2500/2310-Sum-of-Numbers-With-Units-Digit-K/cpp-2310/) | | |
 | | | | | | |
 | 2312 | [Selling Pieces of Wood](https://leetcode.com/problems/selling-pieces-of-wood/) | [无] | [C++](2001-2500/2312-Selling-Pieces-of-Wood/cpp-2312/) | | |
+| 2313 | [Minimum Flips in Binary Tree to Get Result](https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result/) | [无] | [C++](2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/) | | |
 | | | | | | |
 
 ## 力扣中文站比赛
