Description
Given a binary tree root and a voyage array, flip nodes to match the preorder traversal. Return flipped node values or [-1] if impossible.
Examples
Input:
root = [1,2], voyage = [2,1]Output:
[-1]Explanation:
Cannot match.
Input:
root = [1,2,3,4,5], voyage = [1,3,2,5,4]Output:
[1,2]Explanation:
To match the preorder [1,3,2,5,4], the task requires flip node 1 (swap children 2 and 3) so visiting 3 before 2, then flip node 2 (swap children 4 and 5) so visiting 5 before 4.
Input:
root = [1,2,3], voyage = [1,2,3]Output:
[]Explanation:
The tree already matches the desired preorder traversal [1,2,3], so no flips are needed. Return empty array.
Constraints
- •
1 ≤ n ≤ 100