Leetcode 0889 Construct Binary Tree from Preorder and Postorder Traversal

Problem statement

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

Solution 1

Let us use recursion: note, that first element of preorder traversal is equal to last element of postorder traversal. So let us find k = post.index(pre[1]), it will be the point where we need to split our data. Note, that if k is the element before the last, it means that there is only one children and it can be any of them: left or right.

Complexity

Time complexity is O(n^2), because for each list we need to find index. Space is O(n).

Code

class Solution:
    def constructFromPrePost(self, pre, post):
        if not pre: return None
        node = TreeNode(pre[0])
        if len(pre) == 1: return node
        
        k = post.index(pre[1])  
        node.left  = self.constructFromPrePost(pre[1:k+2], post[:k+1])
        node.right = self.constructFromPrePost(pre[k+2:], post[k+1:])
        return node

Solution 2

Actually, we can do better, if we precalculate indexes in the beginning. Then we can use recur(i0, i1, N) function with parameters pre[i0:i0+N], post[i1:i1+N].

Complexity

Time complexity will be O(n), space is O(h).

Code

class Solution(object):
    def constructFromPrePost(self, pre, post):
        d = {num: i for i, num in enumerate(post)}

        def recur(i0, i1, N):
            if N == 0: return None
            root = TreeNode(pre[i0])
            if N == 1: return root

            L = d[pre[i0+1]] - i1 + 1
            root.left = recur(i0 + 1, i1, L)
            root.right = recur(i0 + L + 1, i1 + L, N - 1 - L)
            return root

        return recur(0, 0, len(pre))