LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal Solution

Master LeetCode problem 889 (Construct Binary Tree from Preorder and Postorder 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.

889. Construct Binary Tree from Preorder and Postorder Traversal

Medium

Array Hash Table Divide and Conquer Tree Binary Tree

Problem Explanation

Explanation:

To construct a binary tree from preorder and postorder traversals, we need to understand the properties of these traversal orders. In a preorder traversal, the root node is visited first, then the left subtree, and finally the right subtree. In a postorder traversal, the left subtree is visited first, then the right subtree, and finally the root node.

By using these properties, we can construct the binary tree recursively. The root of the tree is the first element in the preorder traversal. We then find the index of the root in the postorder traversal. This index divides the postorder array into left and right subtrees. We recursively construct the left and right subtrees using the corresponding elements in the preorder and postorder arrays.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return buildTree(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) return null;

        TreeNode root = new TreeNode(pre[preStart]);
        if (preStart == preEnd) return root;

        int idx = postStart;
        while (post[idx] != pre[preStart + 1]) idx++;

        int len = idx - postStart + 1;
        root.left = buildTree(pre, preStart + 1, preStart + len, post, postStart, idx);
        root.right = buildTree(pre, preStart + len + 1, preEnd, post, idx + 1, postEnd - 1);

        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 889 (Construct Binary Tree from Preorder and Postorder Traversal)?

This page provides optimized solutions for LeetCode problem 889 (Construct Binary Tree from Preorder and Postorder 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 889 (Construct Binary Tree from Preorder and Postorder Traversal)?

The time complexity for LeetCode 889 (Construct Binary Tree from Preorder and Postorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 889 on DevExCode?

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

Back to LeetCode Solutions