LintCode (72) Construct Binary Tree from Inorder and Postorder Traversal

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

Have you met this question in a real interview? 

Yes

Example

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

  2
 / \
1   3

Note

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

和上题inorder 和 preorder一起的解法一样， 其实这种题目的关键在于找到谁是root,

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

/** * 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 inorder : A list of integers that inorder traversal of a tree *@param postorder : A list of integers that postorder traversal of a tree *@return : Root of a tree */ public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { // write your code here return helper(inorder, postorder ,0, inorder.size()-1, 0, inorder.size()-1); } TreeNode* helper(vector<int>& in, vector<int>& post, int ibeg, int iend, int pbeg, int pend) { if (pbeg>pend) return 0; int val=post[pend]; int i; for (i = ibeg; i <= iend; i++ ){ if (in[i]==val) break; } TreeNode* root = new TreeNode(val); root->left = helper(in, post, ibeg, i-1, pbeg, pbeg+i-1-ibeg); root->right = helper(in, post, i+1, iend, pend-iend+i,pend-1); return root; } };