# LeetCode 971: Flip Binary Tree To Match Preorder Traversal

## Problem Restatement

We are given a binary tree and an array `voyage`.

A flip operation at a node swaps its left and right children.

We need to flip the smallest number of nodes so that the preorder traversal of the tree becomes exactly equal to `voyage`.

Preorder traversal visits nodes in this order:

```python
root
left subtree
right subtree
```

If it is possible, return the values of the flipped nodes. The values may be returned in any order. If it is impossible, return:

```python
[-1]
```

The tree has `n` nodes, `n == voyage.length`, `1 <= n <= 100`, and all values in the tree and in `voyage` are unique.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary tree |
| Input | `voyage`, the target preorder traversal |
| Output | Values of nodes to flip, or `[-1]` |
| Flip operation | Swap a node's left and right children |

Example function shape:

```python
def flipMatchVoyage(root: Optional[TreeNode], voyage: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
root = [1, 2]
voyage = [2, 1]
```

Output:

```python
[-1]
```

The preorder traversal must start with the root value `1`, but `voyage` starts with `2`. No flip can change the root value.

Example 2:

```python
root = [1, 2, 3]
voyage = [1, 3, 2]
```

Output:

```python
[1]
```

Flip node `1`, so its children become `3` then `2`. The preorder traversal becomes:

```python
[1, 3, 2]
```

Example 3:

```python
root = [1, 2, 3]
voyage = [1, 2, 3]
```

Output:

```python
[]
```

The preorder traversal already matches `voyage`.

## First Thought: Try Flip Choices

At each node, we could try two possibilities:

1. Do not flip the node.
2. Flip the node.

This gives many possible trees.

But we do not need to try both blindly. Preorder traversal tells us exactly which node must come next.

## Key Insight

During preorder DFS, when we visit a node, its value must match the current value in `voyage`.

After visiting the current node, the next value in `voyage` should be the root of the next subtree we visit.

Normally, we visit the left child first.

So if the left child exists but its value does not match the next value in `voyage`, then the only possible way to match the voyage is to flip the current node and visit the right child first.

This gives a greedy rule:

```python
if node.left exists and node.left.val != voyage[index]:
    flip this node
    visit right first, then left
else:
    visit left first, then right
```

If even this does not work, the match is impossible.

## Algorithm

Use DFS with an index into `voyage`.

1. Start with `index = 0`.
2. Visit the current node.
3. If the node is `None`, return `True`.
4. If `node.val != voyage[index]`, return `False`.
5. Move `index` forward.
6. If the left child exists and its value does not match the next expected value:
   - Record `node.val` as flipped.
   - Visit right child first.
   - Then visit left child.
7. Otherwise:
   - Visit left child first.
   - Then visit right child.
8. If DFS succeeds, return the recorded flips.
9. Otherwise, return `[-1]`.

## Correctness

Preorder traversal always visits the current node before its children. Therefore, when DFS reaches a node, its value must equal the current value in `voyage`. If it does not, no sequence of child flips can fix this mismatch, because flips never change node values or move a child above its parent.

After matching the current node, preorder must next visit one of its children, if any child exists. Without a flip, the left child is visited first. With a flip, the right child is visited first.

If the left child exists and does not match the next expected voyage value, then visiting the left child first cannot work. Since values are unique, the only possible child that can match next is the right child. Therefore, flipping the current node is forced.

If the left child already matches the next expected value, then no flip is needed at this node. Flipping would move a different child first and would break the required preorder order.

Thus, at every node, the algorithm makes the only valid choice. If the traversal completes, the recorded flips produce exactly `voyage`. If the algorithm fails, no valid flip sequence exists.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | The recursion stack depends on tree height |

The output list can contain up to `n` flipped node values.

## Implementation

```python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flipMatchVoyage(
        self,
        root: Optional[TreeNode],
        voyage: list[int],
    ) -> list[int]:
        flips = []
        index = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            nonlocal index

            if node is None:
                return True

            if index >= len(voyage) or node.val != voyage[index]:
                return False

            index += 1

            if (
                node.left is not None
                and index < len(voyage)
                and node.left.val != voyage[index]
            ):
                flips.append(node.val)
                return dfs(node.right) and dfs(node.left)

            return dfs(node.left) and dfs(node.right)

        if dfs(root):
            return flips

        return [-1]
```

## Code Explanation

We store flipped node values here:

```python
flips = []
```

The variable `index` points to the next expected value in `voyage`:

```python
index = 0
```

At each node, we first check the preorder match:

```python
if index >= len(voyage) or node.val != voyage[index]:
    return False
```

If the current node matches, we consume that voyage value:

```python
index += 1
```

Then we decide whether to flip.

If the left child exists but is not the next expected node:

```python
if (
    node.left is not None
    and index < len(voyage)
    and node.left.val != voyage[index]
):
```

we must flip the current node. We record it:

```python
flips.append(node.val)
```

and traverse right before left:

```python
return dfs(node.right) and dfs(node.left)
```

Otherwise, we keep normal preorder:

```python
return dfs(node.left) and dfs(node.right)
```

At the end:

```python
if dfs(root):
    return flips

return [-1]
```

we return the flip list if successful, otherwise `[-1]`.

## Testing

```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root = build_tree([1, 2])
    assert s.flipMatchVoyage(root, [2, 1]) == [-1]

    root = build_tree([1, 2, 3])
    assert s.flipMatchVoyage(root, [1, 3, 2]) == [1]

    root = build_tree([1, 2, 3])
    assert s.flipMatchVoyage(root, [1, 2, 3]) == []

    root = build_tree([1, 2, 3, 4, 5])
    assert s.flipMatchVoyage(root, [1, 2, 5, 4, 3]) == [2]

    root = build_tree([1, 2, 3, None, None, 4])
    assert s.flipMatchVoyage(root, [1, 3, 4, 2]) == [1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Root mismatch | Impossible immediately |
| Flip at root | Basic forced flip |
| Already matching preorder | No flips needed |
| Flip below root | Checks recursive flip decision |
| Right subtree before left subtree | Checks normal use of flipped order |