Flip Binary Tree To Match Preorder Traversal

Tested Python solution for LeetCode 971 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 971, Medium. Topics: Tree, Depth-First Search, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 971   # by problem number
lcpy gen -s flip_binary_tree_to_match_preorder_traversal   # by problem name

​

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

​

Examples

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.

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.

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

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h)
    def flip_match_voyage(self, root: TreeNode[int] | None, voyage: list[int]) -> list[int]:
        flipped: list[int] = []
        idx = 0

        def dfs(node: TreeNode[int] | None) -> bool:
            nonlocal idx
            if node is None:
                return True
            if idx >= len(voyage) or node.val != voyage[idx]:
                return False
            idx += 1
            left, right = node.left, node.right
            if left is not None and right is not None:
                if idx >= len(voyage):
                    return False
                if left.val != voyage[idx] and right.val == voyage[idx]:
                    flipped.append(node.val)
                    left, right = right, left
            return dfs(left) and dfs(right)

        if root is None or not dfs(root) or idx != len(voyage):
            return [-1]
        return flipped

​

Complexity

Time	Space
O(n)	O(h)

​

Tags