Boolean Expression Results After Leaf Flips
Problem statement
A Boolean expression tree is encoded by parallel arrays tokens and parent. Node 0 is the root. Operator tokens are AND, OR, XOR, and NOT; leaf tokens are 0 and 1.
Children appear in increasing node-index order. NOT has one child, each other operator has two children, and leaves have none.
Return an array containing the original root value followed by the root value obtained when each leaf is flipped independently. Process leaves in increasing node-index order, and restore the original tree before considering the next leaf.
Function
rootValuesAfterLeafFlips(tokens: String[], parent: int[]) → boolean[]Examples
Example 1
tokens = ["AND","OR","1","0","NOT","0"]parent = [-1,0,1,1,0,4]return = [true,false,true,false]The original expression is (1 OR 0) AND NOT 0, which is true. Flipping leaves 1, 0, and the child of NOT independently produces false, true, and false.
Example 2
tokens = ["XOR","0","0"]parent = [-1,0,0]return = [false,true,true]The original equal inputs XOR to false. Flipping either input alone makes the inputs different.
Constraints
1 <= tokens.length == parent.length <= 200000.parent[0] == -1and0 <= parent[i] < ifori > 0.- The arrays encode one valid rooted expression tree with the required operator arities.
- Every token is
0,1,AND,OR,XOR, orNOT.