Question

2313. Minimum Flips in Binary Tree to Get Result

中文文档

Description

You are given the root of a binary tree with the following properties:

• Leaf nodes have either the value 0 or 1, representing false and true respectively.
• Non-leaf nodes have either the value 2, 3, 4, or 5, representing the boolean operations OR, AND, XOR, and NOT, respectively.

You are also given a boolean result, which is the desired result of the evaluation of the root node.

The evaluation of a node is as follows:

• If the node is a leaf node, the evaluation is the value of the node, i.e. true or false.
• Otherwise, evaluate the node's children and apply the boolean operation of its value with the children's evaluations.

In one operation, you can flip a leaf node, which causes a false node to become true, and a true node to become false.

Return_ the minimum number of operations that need to be performed such that the evaluation of _root_ yields _result. It can be shown that there is always a way to achieve result.

A leaf node is a node that has zero children.

Note: NOT nodes have either a left child or a right child, but other non-leaf nodes have both a left child and a right child.

 

Example 1:

Input: root = [3,5,4,2,null,1,1,1,0], result = true
Output: 2
Explanation:
It can be shown that a minimum of 2 nodes have to be flipped to make the root of the tree
evaluate to true. One way to achieve this is shown in the diagram above.

Example 2:

Input: root = [0], result = false
Output: 0
Explanation:
The root of the tree already evaluates to false, so 0 nodes have to be flipped.

 

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• 0 <= Node.val <= 5
• OR, AND, and XOR nodes have 2 children.
• NOT nodes have 1 child.
• Leaf nodes have a value of 0 or 1.
• Non-leaf nodes have a value of 2, 3, 4, or 5.

Solutions

Solution 1

# 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)]

/**
 * 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};
  }
}

/**
 * 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;
  }
};

/**
 * 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
}

/**
 * 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];
}