Solution: Flip Binary Tree To Match Preorder Traversal

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #971 (Medium): Flip Binary Tree To Match Preorder Traversal

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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].

---

Examples:

Example 1:
Input:	root = [1,2], voyage = [2,1]
Output:	[-1]
Visual:
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]
Visual:
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:	[]
Visual:
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.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In order to find out which nodes have to be flipped, we'll have navigate the binary tree from the root in a pre-order traversal, which is a form of depth first search (DFS), and compare the node values with the values in the voyage array (V).

As with most binary tree DFS solutions, the common solution will use a recursive approach. We can use top-level scoped answer array (ans) to store the flipped nodes as well as an index counter (vix) for the current index of V as we traverse through the binary tree.

For our recursive function (dfs), we'll need to first take care of the exit conditions when the recursive function reaches a null node or when we've already found a failure. Then, if the node value is not the one expected, we should set our answer to [-1].

Since we'll need to have parent-level access when we decide on a necessary flip, we should take care of that now before calling the next round of recursion. We can simply check the left node value against the next index of V, and if they're not a match, we should account for the flip by updating ans.

Rather than actually flipping around nodes in the binary tree, however, we can simply simulate the flip by recursing the two branches in reverse order. Otherwise, we can proceed with normal pre-order traversal.

---

Implementation:

Python doesn't deal as easily with top-level scoped variables, so we can just use the first element of our ans array as the V index (vix), and then pass a reference to ans in our recursive function.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

const flipMatchVoyage = function (root, V) {
    let ans = [], vix = 0
    const dfs = node => {
        if (!node || ans[0] === -1) return
        if (node.val !== V[vix++]) ans = [-1]
        else if (node.left && node.left.val !== V[vix]) {
            ans.push(node.val)
            dfs(node.right)
            dfs(node.left)
        } else {
            dfs(node.left)
            dfs(node.right)
        }
    }
    dfs(root)
    return ans
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def flipMatchVoyage(self, root: TreeNode, V: List[int]) -> List[int]:
        ans = [0]
        def dfs(node, V, ans):
            if not node or ans[0] == -1: return
            if node.val != V[ans[0]]: ans[0] = -1
            else:
                ans[0] += 1
                if node.left and node.left.val != V[ans[0]]:
                    ans.append(node.val)
                    dfs(node.right, V, ans)
                    dfs(node.left, V, ans)
                else:
                    dfs(node.left, V, ans)
                    dfs(node.right, V, ans)
        dfs(root, V, ans)
        return ans[:1] if ans[0] == -1 else ans[1:]

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    int vix = 0;
    List<Integer> ans = new ArrayList<>();
    private void dfs(TreeNode node, int[] V) {
        if (node == null || (ans.size() != 0 && ans.get(0) == -1)) return;
        if (node.val != V[vix++])
            ans = new ArrayList<Integer>(Arrays.asList(-1));
        else if (node.left != null && node.left.val != V[vix]) {
            ans.add(node.val);
            dfs(node.right, V);
            dfs(node.left, V);
        } else {
            dfs(node.left, V);
            dfs(node.right, V);
        }
    }
    public List<Integer> flipMatchVoyage(TreeNode root, int[] V) {
        dfs(root, V);
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    int vix = 0;
    vector<int> ans;
    void dfs(TreeNode* node, vector<int>& V) {
        if (!node || (ans.size() && ans[0] == -1)) return;
        if (node->val != V[vix++]) ans = {-1};
        else if (node->left && node->left->val != V[vix]) {
            ans.push_back(node->val);
            dfs(node->right, V);
            dfs(node->left, V);
        } else {
            dfs(node->left, V);
            dfs(node->right, V);
        }
    }
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& V) {
        dfs(root, V);
        return ans;
    }
};