root of a binary tree with n nodes whose values are 1 to n, all distinct. You also get a route: a permutation of 1 to n giving the order in which you want a preorder traversal to visit the nodes (preorder: the node, then its left subtree, then its right subtree).
In one operation you pick a node and swap its left and right subtrees.
Use as few operations as possible so that the preorder equals route, and return the values of the nodes whose children you swapped, in any order. If the route cannot be matched, return [-1].root=tree_node([1, 2, 3, 4]), route=[1, 3, 2, 4] → [1]
Without swaps the preorder is 1, 2, 4, 3. Swapping the children of node 1 gives 1, 3, 2, 4.
root=tree_node([1, 2, None, 3]), route=[1, 3, 2] → [-1]
Node 3 is a child of node 2, so it always comes after 2. The route cannot be matched: [-1].
root=tree_node([2, 1, 3]), route=[2, 1, 3] → []
The preorder already matches the route, so nothing needs to be swapped.
n, all distinctroute is a permutation of 1 to nroot=tree_node([1, 2, 3, 4]), route=[1, 3, 2, 4]
[1]
Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.