Challenge
Challenge
Problem
Solutions
Submissions
Challenge Points: 20
Level: MediumYou’re given a binary tree with unique values 1..n and a target preorder traversal voyage (length n).
You may flip any node (swap its left and right subtrees). Flip the fewest nodes so that the tree’s preorder equals voyage.
Return the list of flipped node values (any order). If impossible, return [-1].
Key idea: Do a preorder walk while tracking an index i in voyage.
If node.val != voyage[i] → impossible.
Otherwise advance i. If the next desired value (at i) is not the current left child’s value (when left exists), we must flip here: record node.val and traverse right then left; else traverse left then right.
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation:
No sequence of flips can make preorder start with 2 when root is 1.
Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation:
Flip at node 1 to swap children; preorder becomes [1,3,2].
Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation:
Already matches; no flips needed.
Accepted:
Submission:
Report an issue
Code
You need toto run or submitYou need toto run or submit
Test Case
Test Result