LeetCode #105 Construct Binary Tree from Preorder and Inorder Traversal

Medium

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

The first element in preorder list is the root element which we can use to divide left children and right children in inorder list. And use recursive approach to construct whole tree.

Complexity

This approach will iterate each node once to recursively build the tree, every build call take O(1)/O(logn) time in average/worst cases, where n denotes to number of nodes in the tree. Therefore, entire approach takes O(n)/O(nlogn) time in average/worst cases.

The calling stack may reach O(logn) depth and it needs O(1) extra space in every call. And it use O(n) to save the hash map. Hence the space complexity is O(logn + n) = O(n).