You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the **desired ****pre-order traversal** of the binary tree.

Any node in the binary tree can be **flipped** by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

Flip the **smallest** number of nodes so that the **pre-order traversal** of the tree **matches** voyage.

Return *a list of the values of all **flipped** nodes. You may return the answer in **any order**. If it is **impossible** to flip the nodes in the tree to make the pre-order traversal match *voyage*, return the list *[-1].

**Example 1:**

**Input:** root = [1,2], voyage = [2,1]
**Output:** [-1]
**Explanation:** It is impossible to flip the nodes such that the pre-order traversal matches voyage.

**Example 2:**

**Input:** root = [1,2,3], voyage = [1,3,2]
**Output:** [1]
**Explanation:** Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

**Example 3:**

**Input:** root = [1,2,3], voyage = [1,2,3]
**Output:** []
**Explanation:** The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.

**Constraints:**

The number of nodes in the tree is n.

n == voyage.length

1 <= n <= 100

1 <= Node.val, voyage[i] <= n

All the values in the tree are

**unique**.All the values in voyage are

**unique**.

**Solution:**

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
int i=0;
stack.push(root);
while(!stack.isEmpty())
{
TreeNode node = stack.pop();
if(node==null) continue;
if(node.val!=voyage[i++]) return Arrays.asList(-1);
if(node.right!=null && node.right.val==voyage[i])
{
if(node.left!=null) result.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
else
{
stack.push(node.right);
stack.push(node.left);
}
}
return result;
}
}
```

## 댓글