Flip Binary Tree To Match Preorder Traversal LeetCode solution in Python

1
# Runtime: 50 ms (Top 21.2%) | Memory: 16.23 MB (Top 89.3%)
2

3

4
class Solution:
5
    def flipMatchVoyage(self, root, voyage):
6

7
        # ------------------------------
8

9
        def dfs(root):
10

11
            if not root:
12
                # base case aka stop condition
13
                # empty node or empty tree
14
                return True
15

16
            ## general cases
17
            if root.val != voyage[dfs.idx]:
18

19
                # current node mismatch, no chance to make correction by flip
20
                return False
21

22
            # voyage index moves forward
23
            dfs.idx += 1
24

25
            if root.left and (root.left.val != voyage[dfs.idx]):
26

27
                # left child mismatch, flip with right child if right child exists
28
                root.right and result.append(root.val)
29

30
                # check subtree in preorder DFS with child node flip
31
                return dfs(root.right) and dfs(root.left)
32

33
            else:
34

35
                # left child match, check subtree in preorder DFS
36
                return dfs(root.left) and dfs(root.right)
37

38
        # --------------------------
39

40
        # flip sequence
41
        result = []
42

43
        # voyage index during dfs
44
        dfs.idx = 0
45

46
        # start checking from root node
47
        good = dfs(root)
48

49
        return result if good else [-1]