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.
# 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)