难度: Hard
Submission
运行时间: 542 ms
内存: 61.2 MB
# 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:
MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}
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]
Explain
此题解采用深度优先搜索（DFS）策略来计算二叉树中达到指定布尔结果（True或False）所需的最小翻转次数。树中的每个节点可能代表一个布尔值（0为False，1为True）或一个逻辑运算符（例如AND, OR, XOR, NOT）。解题思路是自底向上地计算每个节点达到True或False状态所需的最小翻转次数。对于逻辑运算符，会考虑其左右子树的状态，并计算出所有可能状态的翻转次数，保留最小值。最终，根据根节点的运算结果，返回达到目标结果'True'或'False'的最小翻转次数。
时间复杂度: O(n)
空间复杂度: O(n) in the worst case
# 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:
MAPPING = {0: False, 1: True, 2: or_, 3: and_, 4: xor, 5: not_}
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:
# 如果是NOT运算符，翻转左或右子树的结果
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]
Explore
是的，`MAPPING`映射意味着二叉树中的节点值直接对应于特定的布尔值或布尔运算。对于节点值为2, 3, 4, 5： - `2: or_` 表示当前节点执行逻辑或操作。该节点的最终值由其左右子节点的布尔值通过逻辑或运算确定。 - `3: and_` 表示执行逻辑与操作，节点值由左右子节点通过逻辑与运算确定。 - `4: xor_` 表示执行逻辑异或操作，节点值由左右子节点通过逻辑异或运算确定。 - `5: not_` 表示逻辑非操作，但通常应用于单个子节点（左子节点或右子节点）。这在树的表示中应被明确，即非运算符节点将只有一个子节点。在处理这些运算时，我们基于子节点的逻辑状态计算达到目标状态（True或False）的最小翻转次数。
这种方法假设`NOT`运算符节点总是只有一个子节点。在常规的逻辑运算树表示中，非运算通常只对一个操作数（即一个子节点）应用。因此，代码中考虑左子节点或右子节点的存在性是为了处理某些特殊情况。如果存在右子树而没有左子树，代码通过`if root.left else dfs(root.right)`确保正确地处理了这一情况，即如果左子树不存在，则会使用右子树的结果进行运算。
在处理逻辑运算符节点时，考虑所有可能的左右子树状态组合是因为每种组合可能导致不同的翻转需求，从而影响达到目标状态（True或False）的最小翻转次数。这种方法确保了无论子树的当前状态如何，都能找到达到期望结果的最优解。尽管这种方法在某些情况下可能看起来效率不高，但它确保了全面性和正确性，特别是在树的结构和节点值的变化复杂时。对于优化，可以考虑使用动态规划或者备忘录技术来缓存已计算的结果，避免重复的计算，从而提高效率。