971. Flip Binary Tree To Match Preorder Traversal

Problem

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 (Java)

/**
 * 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 {
    private List<Integer> list = new ArrayList<>();
    private int preIndex = 0;
    private boolean isFlipPossible = true;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        list.clear();
        preIndex = 0;
        isFlipPossible = true;
        traverse(root, voyage);
        if (!isFlipPossible) {
            list.clear();
            list.add(-1);
        }
        return list;
    }

    private void traverse(TreeNode root, int[] voyage) {
        if (root == null) {
            return;
        }
        if (root.val != voyage[preIndex]) {
            isFlipPossible = false;
        } else {
            if (preIndex + 1 < voyage.length
                    && root.left != null
                    && root.left.val != voyage[preIndex + 1]) {
                // swap
                list.add(root.val);
                TreeNode temp = root.right;
                root.right = root.left;
                root.left = temp;
            }
            preIndex++;
            traverse(root.left, voyage);
            traverse(root.right, voyage);
        }
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).