971. Flip Binary Tree To Match Preorder Traversal LeetCode Solution

In this guide, you will get 971. Flip Binary Tree To Match Preorder Traversal LeetCode Solution with the best time and space complexity. The solution to Flip Binary Tree To Match Preorder Traversal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Flip Binary Tree To Match Preorder Traversal solution in C++
Flip Binary Tree To Match Preorder Traversal solution in Java
Flip Binary Tree To Match Preorder Traversal solution in Python
Additional Resources

971. Flip Binary Tree To Match Preorder Traversal LeetCode Solution image

Problem Statement of Flip Binary Tree To Match Preorder Traversal

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:

The number of nodes in the tree is n.
n == voyage.length
1 <= n <= 100
1 <= Node.val, voyage[i] <= n
All the values in the tree are unique.
All the values in voyage are unique.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

971. Flip Binary Tree To Match Preorder Traversal LeetCode Solution in C++

class Solution {
 public:
  vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
    vector<int> ans;
    dfs(root, 0, voyage, ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, int&& i, const vector<int>& voyage,
           vector<int>& ans) {
    if (root == nullptr)
      return;
    if (root->val != voyage[i++]) {
      ans.clear();
      ans.push_back(-1);
      return;
    }

    if (i < voyage.size() && root->left && root->left->val != voyage[i]) {
      // Flip the root.
      ans.push_back(root->val);
      dfs(root->right, std::move(i), voyage, ans);
      dfs(root->left, std::move(i), voyage, ans);
    } else {
      dfs(root->left, std::move(i), voyage, ans);
      dfs(root->right, std::move(i), voyage, ans);
    }
  }
};
/* code provided by PROGIEZ */

971. Flip Binary Tree To Match Preorder Traversal LeetCode Solution in Java

class Solution {
  public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
    List<Integer> ans = new ArrayList<>();

    dfs(root, voyage, ans);

    return ans;
  }

  private int i = 0;

  private void dfs(TreeNode root, int[] voyage, List<Integer> ans) {
    if (root == null)
      return;
    if (root.val != voyage[i++]) {
      ans.clear();
      ans.add(-1);
      return;
    }

    if (i < voyage.length && root.left != null && root.left.val != voyage[i]) {
      // Flip the root.
      ans.add(root.val);
      dfs(root.right, voyage, ans);
      dfs(root.left, voyage, ans);
    } else {
      dfs(root.left, voyage, ans);
      dfs(root.right, voyage, ans);
    }
  }
}
// code provided by PROGIEZ