FunctionRacerProblemsRace

Fewest Leaf Flips

HardTreesPython, JavaScript, TypeScript, Java, C++

You are given the root of a binary tree that stands for a yes or no formula.

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

root [2,3,5,0,1,1]
want true
returns 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

root [3,2,4,0,0,1,1]
want true
returns 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

root [1]
want true
returns 0

The leaf already is what is wanted.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Trees problems