BinarySearch 0325 Tree From Pre/Inorder Traversals

Problem statement

https://binarysearch.com/problems/Tree-From-PreInorder-Traversals/

Solution

Equal to Leetcode 0105. Construct Binary Tree from Preorder and Inorder Traversal.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, preorder, inorder):
        def helper(pr_beg, pr_end, in_beg, in_end):
            if pr_end - pr_beg <= 0: return None
            ind = dic[preorder[pr_beg]]
            root = Tree(inorder[ind])  
            root.left  = helper(pr_beg + 1, pr_beg + 1 + ind - in_beg, in_beg, ind)
            root.right = helper(pr_beg + ind - in_beg + 1, pr_end, ind + 1, in_end)
            return root
        
        dic = {elem: it for it, elem in enumerate(inorder)}  
        return helper(0, len(preorder), 0, len(inorder))