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

Problem statement:

You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.

Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

closed_paren

Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.

Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].

Solution:

For me it was not medium problem, more like hard. First of all it is asked in problem statement to find the minimum number of flips, however in fact we do not have choice: I think everything is determenistic here. The first thing you need to think about when you see tree, it is dfs or bfs. Let us choose recursive dfs, it is usally easier to code and understand.

  1. self.ans is our list with flipped nodes.
  2. self.ind is where exaclty at our voyage array we are now. This is tricky part! If you do not use something similar, you still can solve problem, but it will be more like O(n^2) complexity.

dfs(node) function will work recursively as usual.

  1. Check if we go outside our tree or we out of elements in voyage, in this case we just go back.
  2. Also, we expect, that value of current node we are in now is equal to element we are currently in voyage: if it is not the case, no flipping can save this situation. So, if we see that this condition does not hold, we add None to the answer and return. In the end we going to check if we have None in answer or not.
  3. Define dr = 1: direction of traversal (means left -> right and -1 means right -> left), also increase self.ind by one.
  4. Check if we need to do flip: we need if node.left.val is not equal to voyage[self.ind]: in this case what is expected to be next node in traversal is not equal to the next node in voyages. We add node to answer and change direction. Note, that in the opposite case we can not flip this node, that is everything is determenistic.
  5. Traverse children in right direction and run dfs(child).
  6. In the end, run dfs(root) and check if we have None inside, if we have it means that at one moment of time we have impossible option and we need to return [-1]. In opposite case we return self.ans.

Complexity:

What we did here is just traversed our tree, using dfs, so time complexity is O(n), where n is number of nodes in tree. Space complexity is potentially O(n) as well.

Code

class Solution:
    def flipMatchVoyage(self, root, voyage):
        self.ans, self.ind = [], 0
        
        def dfs(node):
            if not node or self.ind == len(voyage): return
            if node.val != voyage[self.ind]: 
                self.ans.append(None)
                return
            dr, self.ind = 1, self.ind + 1
            
            if node.left and node.left.val != voyage[self.ind]:
                self.ans.append(node.val)
                dr = -1
                
            for child in [node.left, node.right][::dr]:
                dfs(child)
                
        dfs(root)
        return [-1] if None in self.ans else self.ans

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!

If you like the solution, you can upvote it on leetcode discussion section: Problem 0971