LeetCode Solutions Blog

Flip Binary Tree To Match Preorder Traversal

Number: 1011

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given the root of a binary tree where each node has a unique value from 1 to n and a target preorder traversal sequence (voyage), flip the minimum number of nodes so that the tree’s preorder traversal matches the given voyage. A flip at a node means swapping its left and right children. Return the list of node values where flips occurred. If it is impossible to achieve the target preorder traversal, return [-1].

Key Insights

Use a depth-first (preorder) traversal to compare the tree with the voyage.
Maintain an index pointer for the voyage to check current expected values.
If the left child's value does not match the next expected value but the right child's value does, flip the children.
Record the node value where the flip occurred.
Return [-1] as soon as a mismatch is found that cannot be fixed with a flip.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes (each node is visited once).
Space Complexity: O(n), due to recursion stack in the worst case (skewed tree).

Solution

The solution uses a recursive DFS approach to traverse the tree in preorder. During the traversal, if the current tree node's value doesn’t match the expected value from the voyage, it immediately returns false indicating an impossible match. When the subtree rooted at the left child does not match the subsequent voyage value, the algorithm checks if the right child matches. If it does, a flip is performed (swapping left and right) and the node’s value is recorded. The DFS continues recursively on both children. If at any point the match fails, the entire process returns [-1].

Code Solutions

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

class Solution:
    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
        self.voyage = voyage   # target preorder traversal
        self.idx = 0           # pointer to current index in voyage
        self.flips = []        # list to record nodes where flips occur

        def dfs(node):
            if not node:
                return True
            # Check if current node matches the expected voyage value
            if node.val != self.voyage[self.idx]:
                return False
            self.idx += 1
            # If left child exists and its value does not match the next expected value,
            # check if a flip is needed by comparing right child's value.
            if node.left and self.idx < len(self.voyage) and node.left.val != self.voyage[self.idx]:
                if node.right and node.right.val == self.voyage[self.idx]:
                    self.flips.append(node.val)  # record the flip
                    node.left, node.right = node.right, node.left  # perform the flip
                else:
                    return False
            # Recursively process left and right children
            if not dfs(node.left):
                return False
            if not dfs(node.right):
                return False
            return True

        # If DFS fails to match the voyage, return [-1]; otherwise, return recorded flips.
        return self.flips if dfs(root) else [-1]