1018. Binary Prefix Divisible By 5

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
        """
        main idea:
        global idx indicates next integer in voyage;
        if current node is None: means we reach to the bottom, return True 
        if current node.val != v[i], means parent node value wrong instead of two children node, can't swap => return False 
        if current left child exist but not expected value, flip with right child 
        note here we don't check cur.right since we can't ensure position of cur.right, but in preorder traversal left cur is right after parent node 
        tc O(N) sc O(N)
        no need to check if idx overflow since in the description len(voyage) == # of nodes 
        
        """
        self.i = 0
        self.res = [] 
        def dfs(cur):
            if not cur: # reach the bottom 
                return True
            if cur.val != voyage[self.i]:
                return False
            self.i += 1
            if cur.left and cur.left.val != voyage[self.i]: # need to swap 
                self.res.append(cur.val)
                #cur.left,cur.right = cur.right,cur.left 
                return dfs(cur.right) and dfs(cur.left)
            return dfs(cur.left) and dfs(cur.right)
             
        
        return self.res if dfs(root) else [-1]