golang 解法, 执行用时: 248 ms, 内存消耗: 73.9 MB, 提交时间: 2023-10-21 19:49:43

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimumFlips(root *TreeNode, result bool) int {
    const (
        FALSE = iota
        TRUE
        OR
        AND
        XOR
        NOT
    )
    var dfs func(node *TreeNode)[]int
    dfs = func(node *TreeNode)[]int{
        if node == nil{
            return []int{0,0}
        }
        if node.Left == nil && node.Right == nil{
            if node.Val == FALSE{
                return []int{0, 1}
            }else{
                return []int{1, 0}
            }
        }
        ret := make([]int, 2)
        switch node.Val{
        case OR:
            l, r := dfs(node.Left), dfs(node.Right)
            ret[FALSE] = l[FALSE] + r[FALSE]
            ret[TRUE] = min(l[TRUE] + r[TRUE], l[FALSE] + r[TRUE], l[TRUE] + r[FALSE])
        case AND:
            l, r := dfs(node.Left), dfs(node.Right)
            ret[FALSE] = min(l[FALSE]+r[FALSE], l[FALSE]+r[TRUE], l[TRUE]+r[FALSE])
            ret[TRUE] = l[TRUE] + r[TRUE]
        case XOR:
            l, r := dfs(node.Left), dfs(node.Right)
            ret[TRUE] = min(l[FALSE]+r[TRUE], l[TRUE]+r[FALSE])
            ret[FALSE] = min(l[FALSE]+r[FALSE], l[TRUE] + r[TRUE])
        case NOT:
            if node.Left != nil{
                l := dfs(node.Left)
                ret[TRUE] = l[FALSE]
                ret[FALSE] = l[TRUE]
            }else{
                r := dfs(node.Right)
                ret[TRUE] = r[FALSE]
                ret[FALSE] = r[TRUE]
            }
        }
        return ret
    }
    ans := dfs(root)
    if result == true{
        return ans[TRUE]
    }
    return ans[FALSE]
}

func min(nums ...int)int{
    m := nums[0]
    for _, c := range nums{
        if m > c{
            m = c
        }
    }
    return m
}

golang 解法, 执行用时: 344 ms, 内存消耗: 48.5 MB, 提交时间: 2023-10-21 19:49:18

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
const (
	FALSE = iota
	TRUE
	OR
	AND
	XOR
	NOT
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func minimumFlips(root *TreeNode, result bool) int {
	var dp func(root *TreeNode, result int) int
	cache := [2]map[*TreeNode]int{{}, {}}
	dp = func(root *TreeNode, result int) int {
		if temp, ok := cache[result][root]; ok {
			return temp
		}
		var ans int
		switch root.Val {
		case TRUE:
			if result == TRUE {
				return 0
			}
			return 1
		case FALSE:
			if result == TRUE {
				return 1
			}
			return 0
		case OR:
			if result == TRUE {
				ans = min(dp(root.Left, TRUE), dp(root.Right, TRUE))
			} else {
				ans = dp(root.Left, FALSE) + dp(root.Right, FALSE)
			}
		case NOT:
			var child = root.Left
			if child ==nil{
				child = root.Right
			}
			ans = dp(child, result^TRUE)
		case AND:
			if result == TRUE {
				ans = dp(root.Left, TRUE) + dp(root.Right, TRUE)
			} else {
				ans = min(dp(root.Left, FALSE), dp(root.Right, FALSE))
			}
		case XOR:
			if result == TRUE {
				ans = min(dp(root.Left, TRUE)+dp(root.Right, FALSE), dp(root.Left, FALSE)+dp(root.Right, TRUE))
			} else {
				ans = min(dp(root.Left, TRUE)+dp(root.Right, TRUE), dp(root.Left, FALSE)+dp(root.Right, FALSE))
			}
		}
		cache[result][root] = ans
		return ans
	}
	if result {
		return dp(root, TRUE)
	}
	return dp(root, FALSE)
}

cpp 解法, 执行用时: 632 ms, 内存消耗: 348.5 MB, 提交时间: 2023-10-21 19:48:37

/**
 * 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) {}
 * };
 */
// dp[s][c] 表示子树 c 得到状态 s 的最少次数
class Solution {
public:
    const int INF = 0x3f3f3f3f;
    unordered_map<TreeNode*, int> dp[2];
    int dfs(TreeNode* c, int s) {
        if (dp[s].count(c)) return dp[s][c];
        if (c->val < 2) {
            if (c->val != s) dp[s][c] = 1;
            else dp[s][c] = 0;
        } else {
            int res = INF;
            if (c->val == 5) {
                // not
                if (c->left) res = dfs(c->left, !s);
                else res = dfs(c->right, !s);
            } else {
                for (int i = 0; i < 2; ++i) {
                    for (int j = 0; j < 2; ++j) {
                        if (c->val == 2 && (i | j) == s) res = min(res, dfs(c->left, i) + dfs(c->right, j));
                        else if (c->val == 3 && (i & j) == s) res = min(res, dfs(c->left, i) + dfs(c->right, j));
                        else if (c->val == 4 && (i ^ j) == s) res = min(res, dfs(c->left, i) + dfs(c->right, j));
                    }
                }
            }
            dp[s][c] = res;
        }
        return dp[s][c];
    }
    int minimumFlips(TreeNode* root, bool result) {
        // 2 - or
        // 3 - and
        // 4 - xor
        // 5 - not
        return dfs(root, result);
    }
};

cpp 解法, 执行用时: 208 ms, 内存消耗: 179.2 MB, 提交时间: 2023-10-21 19:48:22

/**
 * 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) {}
 * };
 */
// 返回 {生成 1 的最少次数， 生成 0 的最少次数}
class Solution {
public:
    const int INF = 0x3f3f3f3f;
    pair<int, int> dfs(TreeNode* c) {
        if (c->val < 2) {
            return {c->val ^ 1, c->val};
        } else {
            int res = INF;
            if (c->val == 5) {
                // not
                pair<int, int> t;
                if (c->left) t = dfs(c->left);
                else t = dfs(c->right);
                return {t.second, t.first};
            } else {
                auto t1 = dfs(c->left);
                auto t2 = dfs(c->right);
                if (c->val == 2) {
                    // or
                    return {
                        min(t1.first + t2.first,
                            min(t1.second + t2.first, t1.first + t2.second)
                        ), t1.second + t2.second
                    };
                } else if (c->val == 3) {
                    // and
                    return {
                        t1.first + t2.first, min(
                            t1.first + t2.second, min(
                                t1.second + t2.first, t1.second + t2.second
                            )
                        )
                    };
                } else if (c->val == 4) {
                    // xor
                    return {
                        min(t1.first + t2.second, t1.second + t2.first), 
                        min(t1.first + t2.first, t1.second + t2.second)
                    };
                }
            }
        }
        return {-1, -1};
    }
    int minimumFlips(TreeNode* root, bool result) {
        auto t = dfs(root);
        if (result) return t.first;
        return t.second;
    }
};

java 解法, 执行用时: 17 ms, 内存消耗: 74.3 MB, 提交时间: 2023-10-21 19:47:52

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
        private final int FALSE = 0;
        private final int TRUE = 1;
        private final int OR = 2;
        private final int AND = 3;
        private final int XOR = 4;
        private final int NOT = 5;

        public int minimumFlips(TreeNode root, boolean result) {
            int[] ans = getTime(root);
            return result?ans[0]:ans[1];
        }

        private int[] getTime(TreeNode root){
            if(root==null) return new int[]{0,0};
            if(root.val == TRUE || root.val == FALSE) {
                return root.val==TRUE?new int[]{0,1}:new int[]{1,0};
            }
            int[] lRes = getTime(root.left);
            int[] rRes = getTime(root.right);
            switch (root.val){
                case OR: return new int[]{Math.min(lRes[0],rRes[0]),lRes[1]+rRes[1]};
                case AND: return new int[]{lRes[0]+rRes[0],Math.min(lRes[1],rRes[1])};
                case XOR: return new int[]{Math.min(lRes[0]+rRes[1],lRes[1]+rRes[0]),Math.min(lRes[0]+rRes[0],lRes[1]+rRes[1])};
                case NOT: return new int[]{lRes[1]+rRes[1],lRes[0]+rRes[0]};
            }
            return new int[]{0,0};
        }
        
    }

python3 解法, 执行用时: 876 ms, 内存消耗: 143.1 MB, 提交时间: 2023-10-21 19:47:29

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}
INF = int(1e20)

class Solution:
    def minimumFlips(self, root: Optional['TreeNode'], result: bool) -> int:
        """树的叶子为操作数，树的非叶子为运算符，求叶子节点的最小翻转次数"""

        def dfs(root: Optional['TreeNode']) -> List[int]:
            """返回(变为FALSE的最小操作次数,变为TRUE的最小操作次数)"""
            if not root:
                return [INF, INF]
            if root.val in (0, 1):
                return [int(root.val == 1), int(root.val == 0)]
            if root.val == 5:
                return dfs(root.left)[::-1] if root.left else dfs(root.right)[::-1]

            res, leftRes, rightRes = [INF, INF], dfs(root.left), dfs(root.right)
            for left, leftFlip in enumerate(leftRes):
                for right, rigthFlip in enumerate(rightRes):
                    value = MAPPING[root.val](left, right)
                    res[value] = min(res[value], leftFlip + rigthFlip)

            return res

        return dfs(root)[result & 1]