Leetcode 1011 Solution

This article provides solution to leetcode question 1011 (flip-binary-tree-to-match-preorder-traversal)
Categories:
Tags:
Access this page by simply typing in "lcs 1011" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal

Solution

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

class Solution(object):
    def flipMatchVoyage(self, root, voyage):
        """
        :type root: TreeNode
        :type voyage: List[int]
        :rtype: List[int]
        """
        self.ans = []
        self.success = False
        self.i = 0

        def dfs(root, preorder):
            if root is None and self.i == len(preorder):
                self.success = True
                return

            if root is None or self.i == len(preorder):
                return

            if root.val != preorder[self.i]:
                return

            self.i += 1

            if root.right and root.right.val == preorder[self.i]:
                dfs(root.right, preorder)
                dfs(root.left, preorder)
                if root.left:
                    self.ans.append(root.val)
            else:
                dfs(root.left, preorder)
                dfs(root.right, preorder)

        dfs(root, voyage)
        return self.ans if self.success else [-1]