Fewest Leaf Flips
You are given the root of a binary tree that stands for a yes or no formula.
- A leaf holds 0 (false) or 1 (true).
- A node with two children holds 2 (OR), 3 (AND) or 4 (XOR) and combines the results of its two children.
- A node with exactly one child holds 5 (NOT) and turns the result of that child around.
One flip changes a leaf from 0 to 1 or from 1 to 0. Return the fewest flips after which the whole tree comes out as want.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
AND of 0 and 1 is false, NOT 1 is false, so the OR is false. Flipping the leaf 0 makes the AND true, and that is enough.
Example 2
Both the OR and the XOR come out false, and the AND needs both to be true: one flip on each side.
Example 3
The leaf already is what is wanted.
Constraints
1 <= number of nodes <= 40, and the tree follows the rules abovewantisTrueorFalse
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.