Lintcode: Construct Binary Tree from Preorder and Inorder Traversal

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

Have you met this question in a real interview? 

Yes

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

  2
 / \
1   3

Note

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

Tags Expand 

Binary Tree

thoughts:
http://fisherlei.blogspot.com/2013/01/leetcode-construct-binary-tree-from.html
codes:
http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html
clear codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-construct-binary-tree-from_11.html

The key is to look for root and create tree recursively
Note the margin condition!!
 http://scyforce.gitbooks.io/leetcode/content/construct_binary_tree_from_preorder_and_inorder_traversal.html (see the margin condition)

Line 32 - 37 are for loop to look for element in array which can be replaced by a hashmap

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { /** *@param preorder : A list of integers that preorder traversal of a tree *@param inorder : A list of integers that inorder traversal of a tree *@return : Root of a tree */ public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { // write your code here int n = inorder.size(); return buildTree(preorder, inorder, 0, n - 1, 0, n - 1); } TreeNode* buildTree(vector<int> &preorder, vector<int> &inorder, int s1, int e1, int s2, int e2){ if(e1 < s1 || e2 < s2) return NULL; TreeNode *root = new TreeNode(preorder[s1]); int rootIndex = -1; for(int i = s2; i <= e2; i++){ if(inorder[i] == root->val) { rootIndex = i; break; } } //if(rootIndex == -1) return NULL; int leftTreeSize = rootIndex - s2; int rightTreeSize = e2 - rootIndex; root->left = buildTree(preorder, inorder, s1 + 1, s1 + leftTreeSize, s2, s2 + leftTreeSize - 1); root->right = buildTree(preorder, inorder, s1 + 1 + leftTreeSize, e1, rootIndex + 1, e2); return root; } };