Introduction

In this blog post, we will explore how to solve the LeetCode problem "889" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree. If there exist multiple answers, you can return any of them. Example 1: Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7] Example 2: Input: preorder = [1], postorder = [1] Output: [1] Constraints: 1 <= preorder.length <= 30 1 <= preorder[i] <= preorder.length All the values of preorder are unique. postorder.length == preorder.length 1 <= postorder[i] <= postorder.length All the values of postorder are unique. It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Explanation

Here's the breakdown of the solution:

• Root Identification: The first element of the preorder array is always the root of the (sub)tree. The last element of the postorder array is also the root of the (sub)tree.
• Left Subtree Boundary: Find the index of the left child (the second element in preorder) in postorder. Everything to the left of this index forms the left subtree in postorder. The size of the left subtree can be inferred.

• Recursive Construction: Recursively construct the left and right subtrees using the identified boundaries in both preorder and postorder arrays.

• Time & Space Complexity: O(N), where N is the number of nodes in the tree. Space complexity is O(N) due to the recursion stack.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructFromPrePost(preorder, postorder):
    """
    Reconstructs a binary tree from its preorder and postorder traversals.

    Args:
        preorder: A list of integers representing the preorder traversal.
        postorder: A list of integers representing the postorder traversal.

    Returns:
        The root of the reconstructed binary tree.
    """

    def buildTree(pre_start, pre_end, post_start, post_end):
        if pre_start > pre_end:
            return None

        root_val = preorder[pre_start]
        root = TreeNode(root_val)

        if pre_start == pre_end:
            return root

        left_child_val = preorder[pre_start + 1]
        left_child_index_in_post = postorder.index(left_child_val)

        left_subtree_size = left_child_index_in_post - post_start + 1

        root.left = buildTree(
            pre_start + 1, pre_start + left_subtree_size,
            post_start, left_child_index_in_post
        )

        root.right = buildTree(
            pre_start + left_subtree_size + 1, pre_end,
            left_child_index_in_post + 1, post_end - 1
        )

        return root

    return buildTree(0, len(preorder) - 1, 0, len(postorder) - 1)