Flip Binary Tree To Match Preorder Traversal

Problem Id: 971 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

All the node is different. So to do the minimum flips, we only need to do necessary.

For example, if voyage is [1, 2] while the tree looks like below:

  1
 /
2

Then, it is not necessary to flip children of node 1 and node 2. Even if we flip any of it, the result tree still has preorder [1, 2].

But for tree like below with voyage [1, 3, 2], we must flip the node 1:

  1
 / \
2   3

So, the logic is that, for each left node, if the next value in the voyage is not the same with the node's value, then we flip the node. And if the right node is also not the next value in the voyage, it is impossible to get the voyage by flipping the original tree.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
        self.index = 0
        self.result = []
        self.reachable = True
        self.voyage = voyage
        self._helper(root)
        if not self.reachable:
            return [-1]
        return self.result

    def _helper(self, node):
        if node is None or not self.reachable:
            return
        if self.index >= len(self.voyage) or node.val != self.voyage[self.index]:
            self.reachable = False
            return
        self.index += 1
        if self.index < len(self.voyage) and node.left \
                and node.left.val != self.voyage[self.index]:
            self.result.append(node.val)
            node.left, node.right = node.right, node.left
        self._helper(node.left)
        self._helper(node.right)