Solution


Intuition

As we do a pre-order traversal, we will flip nodes on the fly to try to match our voyage with the given one.

If we are expecting the next integer in our voyage to be voyage[i], then there is only at most one choice for path to take, as all nodes have different values.

Algorithm

Do a depth first search. If at any node, the node's value doesn't match the voyage, the answer is [-1].

Otherwise, we know when to flip: the next number we are expecting in the voyage voyage[i] is different from the next child.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given tree.

  • Space Complexity: .


Analysis written by: @awice.