Sponsored
Sponsored
The idea is to use a recursive approach that performs a pre-order traversal, comparing each visited node with the corresponding value in the voyage sequence. If the current node's value doesn't match, it may be necessary to flip its children and recheck. The goal is to flip the minimum number of nodes such that the tree's pre-order traversal matches the given voyage. If impossible, return [-1].
Time Complexity: O(n) since we traverse all nodes in the binary tree once.
Space Complexity: O(h) due to the recursion call stack, where h is the height of the tree.
1var flipMatchVoyage = function(root, voyage) {
2 let res = [], i = 0;
3 function dfs(node) {
4 if (!node) return true;
5 if (node.val !== voyage[i++]) return false;
6 if (node.left && node.left.val !== voyage[i]) {
7 res.push(node.val);
8 return dfs(node.right) && dfs(node.left);
9 }
10 return dfs(node.left) && dfs(node.right);
11 }
12 return dfs(root) ? res : [-1];
13};The JavaScript solution mostly resembles the Python method. We define a helper function dfs that traverses nodes in pre-order. Upon finding a discrepancy between node values and voyage[i], check if flipping solves it. This condition arises when the left child's value isn't the next in the voyage. Track nodes whose flipping rectifies the order. Otherwise, eventually return [-1] when impossible.
This approach uses an explicit stack to simulate a pre-order traversal iteratively and checks against the voyage. The stack helps process nodes similar to recursion, with flipping decisions based on discrepancies between expected and current values.
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(h) where h is the height of the binary tree. The stack size is determined by the deepest path.
1import java.util.*;
2This solution uses an iterative approach to traverse the tree pre-order using a stack. Nodes are pushed on the stack to be processed later. If the node's value doesn't match the current index in voyage, we return [-1]. If the right child's value equals the next entry in voyage, consider flipping the children if a left child exists, and add the flipped node to res. Push children in an order that aligns with the traversal aimed for by voyage.