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:
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].
Example 1:
Input: root = [1,2], voyage = [2,1] Output: [-1] Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
Example 2:
Input: root = [1,2,3], voyage = [1,3,2] Output: [1] Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
Example 3:
Input: root = [1,2,3], voyage = [1,2,3] Output: [] Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.
Constraints:
n.n == voyage.length1 <= n <= 1001 <= Node.val, voyage[i] <= nvoyage are unique.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].
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.
JavaScript
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.
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.
This 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.
C++
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.
| Approach | Complexity |
|---|---|
| Recursive Pre-order Traversal with Flipping | Time Complexity: O(n) since we traverse all nodes in the binary tree once. |
| Iterative Pre-order Traversal with Stack | Time Complexity: O(n) since each node is processed once. |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 307,238 views views
Watch 9 more video solutions →Practice Flip Binary Tree To Match Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor