首页 > 代码库 > Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

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

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

 1 class Solution { 2 public: 3     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { 4         return get_Tree(inorder.begin(),inorder.end(),postorder.begin(),postorder.end()); 5     } 6     TreeNode * get_Tree(vector<int>::iterator in_l, vector<int>::iterator in_r, vector<int>::iterator post_l,vector<int>::iterator post_r){ 7       if(in_l >= in_r || post_l >= post_r) return NULL; 8       TreeNode * root = new TreeNode(*prev(post_r)); 9       vector<int>::iterator loca = find(in_l,in_r,*prev(post_r));10       root->left = get_Tree(in_l,loca,post_l,next(post_l,distance(in_l,loca)));11       root->right = get_Tree(next(loca),in_r,next(post_l,distance(in_l,loca)),prev(post_r));12       return root;13     }14 };