LeetCode 971: Flip Binary Tree To Match Preorder Traversal Solution

Master LeetCode problem 971 (Flip Binary Tree To Match Preorder Traversal), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

971. Flip Binary Tree To Match Preorder Traversal

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a pre-order traversal of the binary tree while checking if the current node's value matches the corresponding value in the voyage array. If the values match, we continue with the traversal. If they do not match, we need to flip the current node by swapping its left and right children. We need to keep track of the nodes that are flipped during the traversal.

Algorithmic Idea:

Perform pre-order traversal of the binary tree.
During traversal, check if the current node's value matches the corresponding value in the voyage array.
If the values do not match, flip the current node by swapping its left and right children.
Keep track of the flipped nodes.
If it is impossible to match the voyage, return [-1]. Otherwise, return the list of flipped nodes.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Solution Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<Integer> result = new ArrayList<>();
    int index = 0;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        if (dfs(root, voyage)) {
            return result;
        } else {
            return List.of(-1);
        }
    }

    private boolean dfs(TreeNode node, int[] voyage) {
        if (node == null) {
            return true;
        }
        
        if (node.val != voyage[index++]) {
            return false;
        }
        
        if (node.left != null && node.left.val != voyage[index]) {
            result.add(node.val);
            return dfs(node.right, voyage) && dfs(node.left, voyage);
        }
        
        return dfs(node.left, voyage) && dfs(node.right, voyage);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 971 (Flip Binary Tree To Match Preorder Traversal)?

This page provides optimized solutions for LeetCode problem 971 (Flip Binary Tree To Match Preorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 971 (Flip Binary Tree To Match Preorder Traversal)?

The time complexity for LeetCode 971 (Flip Binary Tree To Match Preorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 971 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 971 in Java, C++, or Python.

Back to LeetCode Solutions