跳转至

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, 105] 范围内。
  • 0 <= Node.val <= 5
  • OR, AND, XOR 节点有 2 个子节点。
  • NOT 只有一个 1 子节点。
  • 叶节点的值为 0 或 1.
  • 非叶节点的值为2, 3, 4, 5.

解法

方法一：树形 DP + 分情况讨论

我们定义一个函数 $dfs(root)$，它的返回值是一个长度为 $2$ 的数组，其中第一个表示将 $root$ 节点的值变成 false 所需要的最少翻转次数，第二个表示将 $root$ 节点的值变成 true 所需要的最少翻转次数。那么答案为 $dfs(root)[result]$。

函数 $dfs(root)$ 的实现如下：

如果 $root$ 为空，那么返回 $[+\infty, +\infty]$。

否则，我们记 $root$ 的值为 $x$，左子树的返回值为 $l$，右子树的返回值为 $r$，然后分情况讨论：

  • 如果 $x \in {0, 1}$，那么返回 $[x, x \oplus 1]$。
  • 如果 $x = 2$，即布尔运算符是 OR，为了使 $root$ 的值为 false，我们需要将左右子树的值都变成 false，因此返回值的第一个元素为 $l[0] + r[0]$；为了使 $root$ 的值为 true，我们需要将左右子树的值中至少有一个变成 true，因此返回值的第二个元素为 $\min(l[0] + r[1], l[1] + r[0], l[1] + r[1])$。
  • 如果 $x = 3$，即布尔运算符是 AND，为了使 $root$ 的值为 false，我们需要将左右子树的值中至少有一个变成 false，因此返回值的第一个元素为 $\min(l[0] + r[0], l[0] + r[1], l[1] + r[0])$；为了使 $root$ 的值为 true，我们需要将左右子树的值都变成 true，因此返回值的第二个元素为 $l[1] + r[1]$。
  • 如果 $x = 4$，即布尔运算符是 XOR，为了使 $root$ 的值为 false，我们需要将左右子树的值同为 false 或同为 true，因此返回值的第一个元素为 $\min(l[0] + r[0], l[1] + r[1])$；为了使 $root$ 的值为 true，我们需要将左右子树的值不同，因此返回值的第二个元素为 $\min(l[0] + r[1], l[1] + r[0])$。
  • 如果 $x = 5$，即布尔运算符是 NOT，为了使 $root$ 的值为 false，我们需要将左右子树的值中至少有一个变成 true，因此返回值的第一个元素为 $\min(l[1], r[1])$；为了使 $root$ 的值为 true，我们需要将左右子树的值中至少有一个变成 false，因此返回值的第二个元素为 $\min(l[0], r[0])$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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
class Solution:
    def minimumFlips(self, root: Optional[TreeNode], result: bool) -> int:
        def dfs(root: Optional[TreeNode]) -> (int, int):
            if root is None:
                return inf, inf
            x = root.val
            if x in (0, 1):
                return x, x ^ 1
            l, r = dfs(root.left), dfs(root.right)
            if x == 2:
                return l[0] + r[0], min(l[0] + r[1], l[1] + r[0], l[1] + r[1])
            if x == 3:
                return min(l[0] + r[0], l[0] + r[1], l[1] + r[0]), l[1] + r[1]
            if x == 4:
                return min(l[0] + r[0], l[1] + r[1]), min(l[0] + r[1], l[1] + r[0])
            return min(l[1], r[1]), min(l[0], r[0])

        return dfs(root)[int(result)]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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 {
    public int minimumFlips(TreeNode root, boolean result) {
        return dfs(root)[result ? 1 : 0];
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] {1 << 30, 1 << 30};
        }
        int x = root.val;
        if (x < 2) {
            return new int[] {x, x ^ 1};
        }
        var l = dfs(root.left);
        var r = dfs(root.right);
        int a = 0, b = 0;
        if (x == 2) {
            a = l[0] + r[0];
            b = Math.min(l[0] + r[1], Math.min(l[1] + r[0], l[1] + r[1]));
        } else if (x == 3) {
            a = Math.min(l[0] + r[0], Math.min(l[0] + r[1], l[1] + r[0]));
            b = l[1] + r[1];
        } else if (x == 4) {
            a = Math.min(l[0] + r[0], l[1] + r[1]);
            b = Math.min(l[0] + r[1], l[1] + r[0]);
        } else {
            a = Math.min(l[1], r[1]);
            b = Math.min(l[0], r[0]);
        }
        return new int[] {a, b};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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) {
        function<pair<int, int>(TreeNode*)> dfs = [&](TreeNode* root) -> pair<int, int> {
            if (!root) {
                return {1 << 30, 1 << 30};
            }
            int x = root->val;
            if (x < 2) {
                return {x, x ^ 1};
            }
            auto [l0, l1] = dfs(root->left);
            auto [r0, r1] = dfs(root->right);
            int a = 0, b = 0;
            if (x == 2) {
                a = l0 + r0;
                b = min({l0 + r1, l1 + r0, l1 + r1});
            } else if (x == 3) {
                a = min({l0 + r0, l0 + r1, l1 + r0});
                b = l1 + r1;
            } else if (x == 4) {
                a = min(l0 + r0, l1 + r1);
                b = min(l0 + r1, l1 + r0);
            } else {
                a = min(l1, r1);
                b = min(l0, r0);
            }
            return {a, b};
        };
        auto [a, b] = dfs(root);
        return result ? b : a;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimumFlips(root *TreeNode, result bool) int {
    var dfs func(*TreeNode) (int, int)
    dfs = func(root *TreeNode) (int, int) {
        if root == nil {
            return 1 << 30, 1 << 30
        }
        x := root.Val
        if x < 2 {
            return x, x ^ 1
        }
        l0, l1 := dfs(root.Left)
        r0, r1 := dfs(root.Right)
        var a, b int
        if x == 2 {
            a = l0 + r0
            b = min(l0+r1, min(l1+r0, l1+r1))
        } else if x == 3 {
            a = min(l0+r0, min(l0+r1, l1+r0))
            b = l1 + r1
        } else if x == 4 {
            a = min(l0+r0, l1+r1)
            b = min(l0+r1, l1+r0)
        } else {
            a = min(l1, r1)
            b = min(l0, r0)
        }
        return a, b
    }
    a, b := dfs(root)
    if result {
        return b
    }
    return a
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minimumFlips(root: TreeNode | null, result: boolean): number {
    const dfs = (root: TreeNode | null): [number, number] => {
        if (!root) {
            return [1 << 30, 1 << 30];
        }
        const x = root.val;
        if (x < 2) {
            return [x, x ^ 1];
        }
        const [l0, l1] = dfs(root.left);
        const [r0, r1] = dfs(root.right);
        if (x === 2) {
            return [l0 + r0, Math.min(l0 + r1, l1 + r0, l1 + r1)];
        }
        if (x === 3) {
            return [Math.min(l0 + r0, l0 + r1, l1 + r0), l1 + r1];
        }
        if (x === 4) {
            return [Math.min(l0 + r0, l1 + r1), Math.min(l0 + r1, l1 + r0)];
        }
        return [Math.min(l1, r1), Math.min(l0, r0)];
    };
    return dfs(root)[result ? 1 : 0];
}

评论