Flip Binary Tree To Match Preorder Traversal

Problem Statement

Imagine you have a binary tree, uniquely identified by nodes with values ranging from 1 to n. Each node's value is different. Along with the tree structure, you're given a sequence called voyage. This sequence represents how you wish the tree's pre-order traversal would ideally appear.

Your task is to make the fewest number of moves to rearrange— through flipping of nodes—the tree so that its actual pre-order traversal mirrors the voyage sequence provided. A flip involves swapping the left and right child of any node. After altering the tree, if the pre-order traversal matches voyage, you will return the values of the flipped nodes. If matching the sequence is not possible, return [-1]. The flipping operation aims to minimize the number of disrupted nodes while ensuring the traversal order aligns with voyage.

Examples

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.

Approach and Intuition

The given problem can be approached by sequentially comparing the tree's pre-order traversal with the voyage list:

1. Conduct a pre-order traversal on the root, sequentially inspecting nodes against the voyage list.
   • If both current node in the tree and voyage match, move to the next element and node.
   • If there's a mismatch, check possible flip:
     • If flipping the current node results in a sequence that matches the next segment of voyage, the flip is valid. Record the flipped node and continue.
     • If not, it implies flipping cannot aid in matching the sequence, hence return [-1].

Based on provided examples:

• Example 1:

  • Tree=(1->2), Voyage=[2,1]
  • There is no flip possible that will match the voyage sequence, making it impossible to achieve. Thus, the output is [-1].

• Example 2:

  • Tree=(1->2 on the left and 3 on the right), Voyage=[1,3,2]
  • By flipping node 1, the sequence aligns perfectly with the voyage. Hence, node 1 is flipped. The output reflects this flip: [1].

• Example 3:

  • Tree=(1->2 on the left and 3 on the right), Voyage=[1,2,3]
  • The existing tree already matches the desired voyage sequence; therefore, no flips are necessary. We return an empty list [].

With the constraints indicating a manageable number of nodes (1 <= n <= 100), the above approach works efficiently. Ensure to iteratively check each node with the possibility of a flip to either confirm the pre-order traversal can match the voyage or determine that it's impossible early on.

Solutions

class Solution {
    List<Integer> resultReorder;
    int currentIndex;
    int[] traversalOrder;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        resultReorder = new ArrayList<>();
        currentIndex = 0;
        this.traversalOrder = voyage;

        traversePreOrder(root);
        if (!resultReorder.isEmpty() && resultReorder.get(0) == -1) {
            resultReorder.clear();
            resultReorder.add(-1);
        }

        return resultReorder;
    }

    public void traversePreOrder(TreeNode node) {
        if (node != null) {
            if (node.val != traversalOrder[currentIndex++]) {
                resultReorder.clear();
                resultReorder.add(-1);
                return;
            }

            if (currentIndex < traversalOrder.length && node.left != null &&
                    node.left.val != traversalOrder[currentIndex]) {
                resultReorder.add(node.val);
                traversePreOrder(node.right);
                traversePreOrder(node.left);
            } else {
                traversePreOrder(node.left);
                traversePreOrder(node.right);
            }
        }
    }
}