# 105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
Example:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
# Solution
Approach 1: recursion.
# Code (Python)
Approach 1:
class Solution:
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# time: each search takes N, at best logN times, at worse N times, so worse case O(N^2)
return self._build(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
def _build(self, preorder, start1, end1, inorder, start2, end2):
if start1 > end1:
return None
if start1 == end1:
return TreeNode(preorder[start1])
root = TreeNode(preorder[start1])
len_left = inorder.index(root.val, start2) - start2
root.left = self._build(preorder, start1 + 1, start1 + len_left, inorder, start2, start2 + len_left)
root.right = self._build(preorder, start1 + len_left + 1, end1, inorder, start2 + len_left + 1, end2)
return root
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode* doBuildTree(vector<int>& preorder, int pHead, int pTail, vector<int>& inorder, int iHead, int iTail) {
if (pHead > pTail || iHead > iTail)
return NULL;
int i;
for (i = iHead; i <= iTail; ++i)
{
if (inorder[i] == preorder[pHead])
break;
}
int iLeftHead = iHead;
int iLeftTail = i - 1;
int iRightHead = i + 1;
int iRightTail = iTail;
int pLeftHead = pHead + 1;
int pLeftTail = pLeftHead + iLeftTail - iLeftHead;
int pRightHead = pLeftTail + 1;
int pRightTail = pTail;
TreeNode *root = new TreeNode(preorder[pHead]);
root->left = doBuildTree(preorder, pLeftHead, pLeftTail, inorder, iLeftHead, iLeftTail);
root->right = doBuildTree(preorder, pRightHead, pRightTail, inorder, iRightHead, iRightTail);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return doBuildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
};