Flip Binary Tree To Match Preorder Traversal
01 · Problem
You are given the root of a binary tree with n nodes whose values are the distinct integers 1 to n, and an array voyage that is a permutation of those same values.
A flip on a node swaps its left and right child subtrees. You may flip any number of nodes (each at most once). Your goal is to make the preorder traversal of the tree (visit node, then left subtree, then right subtree) equal voyage exactly.
Return the values of all the nodes you flip, in any order. Flip only nodes that actually need it: a node is flipped exactly when its left child's value does not match the next value expected by voyage. If no set of flips can make the traversal match, return [-1].
02 · Examples
root = [1,2], voyage = [2,1]
[-1]
Every preorder traversal starts at the root, which has value 1, but the voyage starts with 2. No set of flips can fix that.
root = [1,2,3], voyage = [1,3,2]
[1]
Flipping node 1 swaps its children, so the preorder becomes 1, 3, 2.
root = [1,2,3,4,5,6,7], voyage = [1,3,7,6,2,4,5]
[1,3]
Flip node 1 so 3 is visited before 2, then flip node 3 so 7 is visited before 6. Node 2's children are already in the right order.
03 · Constraints
- 01The number of nodes in the tree is n, with 1 <= n <= 100.
- 02voyage.length == n
- 031 <= Node.val, voyage[i] <= n
- 04All node values are unique and all values in voyage are unique.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.