2313：二叉树中得到结果所需的最少翻转次数（★★）

Ian

2022-06-20 约 645 字预计阅读 2 分钟次阅读

力扣第 2313 题

题目

给定二叉树的根 root，具有以下属性:

叶节点 的值为 0 或 1，分别表示 false 和 true。
非叶节点的值为 2、3、4、5，分别表示布尔运算 OR, AND, XOR, NOT。

您还将得到一个布尔型 result，这是 root 节点的期望评价结果。

对节点的评价计算如下:

如果节点是叶节点，则评价是节点的值，即 true 或 false.
否则, 将其值的布尔运算应用于子节点的评价，该节点的评价即为布尔运算后的结果。

在一个操作中，您可以翻转一个叶节点，这将导致一个 false 节点变为 true 节点，一个 true 节点变为 false 节点。

返回需要执行的最小操作数，以使 root 的评价得到 result。可以证明，总有办法达到 result。

叶节点 是没有子节点的节点。

注意: NOT 节点只有左孩子或只有右孩子，但其他非叶节点同时拥有左孩子和右孩子。

示例 1:

输入: root = [3,5,4,2,null,1,1,1,0], result = true
输出: 2
解释:
可以证明，至少需要翻转 2 个节点才能使树的 root 评价为 true。上面的图显示了实现这一目标的一种方法。

示例 2:

输入: root = [0], result = false
输出: 0
解释:
树的 root 的评价已经为 false，所以 0 个节点必须翻转。

提示:

树中的节点数在 [1, 10⁵] 范围内。
0 <= Node.val <= 5
OR, AND, XOR 节点有 2 个子节点。
NOT 只有一个 1 子节点。
叶节点的值为 0 或 1.
非叶节点的值为2, 3, 4, 5.

相似问题：

分析

树形 dp，返回子树评价为 0/1 的最小操作数，递推即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:
        def dfs(u):
            if not u.left and not u.right:
                return u.val,u.val^1
            if u.val==5:
                a,b = dfs(u.left or u.right)
                return b,a
            a,b = dfs(u.left),dfs(u.right)
            if u.val==2:
                return a[0]+b[0],min(a[1]+b[0],a[0]+b[1],a[1]+b[1])
            if u.val==3:
                return min(a[0]+b[0],a[0]+b[1],a[1]+b[0]),a[1]+b[1]
            return min(a[0]+b[0],a[1]+b[1]),min(a[0]+b[1],a[1]+b[0])
        return dfs(root)[result]

111 ms

目录

2313：二叉树中得到结果所需的最少翻转次数（★★）

题目

分析

解答