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.
1class Solution:
2 def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
3 self.res, self.i = [], 0
4
5 def dfs(node):
6 if not node:
7 return True
8 if node.val != voyage[self.i]:
9 return False
10 self.i += 1
11 if (node.left and node.left.val != voyage[self.i]):
12 self.res.append(node.val)
13 return dfs(node.right) and dfs(node.left)
14 return dfs(node.left) and dfs(node.right)
15
16 return self.res if dfs(root) else [-1]This solution uses a depth-first search (dfs) recursively to perform a pre-order traversal. First, iterate through the tree with dfs, comparing each current node's value with voyage[i]. If values match, increment the index. When a node is reached whose left child's value does not match the next required voyage entry, flip its children. If no flips can result in an appropriate traversal, return [-1]. Store and return all nodes whose children were flipped.
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.
1#include <vector>
2#include <stack>
3class Solution {
4public:
5 vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
vector<int> res;
stack<TreeNode*> stack;
stack.push(root);
int i = 0;
while (!stack.empty()) {
TreeNode *node = stack.top(); stack.pop();
if (node->val != voyage[i++]) return {-1};
if (node->right && node->right->val == voyage[i]) {
if (node->left) res.push_back(node->val);
stack.push(node->left);
stack.push(node->right);
} else {
stack.push(node->right);
stack.push(node->left);
}
}
return res;
}
};The C++ solution uses iterative traversal employing a stack to simulate recursion. It sequences nodes pre-order in alignment with voyage. Each node checked: if value mismatches the desired voyage, return [-1]. For distinct children, if right precedes left in voyage, effectuate a flip, logging that node, and process via the stack subsequently.