971. Flip Binary Tree To Match Preorder Traversal (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flipMatchVoyage(self, root, voyage):
        """
        :type root: TreeNode
        :type voyage: List[int]
        :rtype: List[int]
        """
        self.result = []
        self.i = 0
        def dfs(root):
            if self.result == [-1]:
                return
            if root:
                if root.val != voyage[self.i]:
                    self.result = [-1]
                    return
                if root.left and root.left.val != voyage[self.i + 1]:
                    root.left, root.right = root.right, root.left
                    self.result.append(root.val)
                self.i += 1
                dfs(root.left)
                self.i += 1
                dfs(root.right)
            else:
                self.i -= 1
        dfs(root)
        return self.result