LintCode (73) 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.

画一下preorder和postorder就可以了

preorder:

|root|  .... left subtree ....| ... right subtree...|

inorder:

|...left subtree ...| root | .... right subtree ...|

所以我们可以用preorder的第一个元素来创建root, 而用 preorder, inorder的左子数创建左孩子，， 右子树创建右孩子， 这个过程是个recursive call

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

/** * 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 return buildHelper(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1); } TreeNode *buildHelper(vector<int>& preorder, vector<int>& inorder, int pbeg, int pend, int ibeg, int iend) { if (pbeg>pend) return 0; int val=preorder[pbeg]; int i; for ( i=ibeg; i<=iend; i++){ if (inorder[i]==val) break; } TreeNode* root=new TreeNode(val); root->left= buildHelper(preorder, inorder, pbeg+1, pbeg+i-ibeg,ibeg, i-1); root->right=buildHelper(preorder, inorder, pend+i-iend+1,pend,i+1, iend); return root; } };