# [LeetCode]*106.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.

```/*--------------------------------------- * 日期：2015-05-01 * 作者：SJF0115 * 题目: 106.Construct Binary Tree from Inorder and Postorder Traversal * 网址：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ * 结果：AC * 来源：LeetCode * 博客： -----------------------------------------*/ #include <iostream> #include <vector> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { int size = inorder.size(); if(size <= 0){ return nullptr; }//if return InPostBuildTree(inorder,postorder,0,size-1,size); } private: TreeNode* InPostBuildTree(vector<int> &inorder,vector<int> &postorder,int inIndex,int postIndex,int size){ if(size <= 0){ return nullptr; }//if // 根节点 TreeNode* root = new TreeNode(postorder[postIndex]); // 寻觅postorder[postIndex]在中序序列中的下标 int index = 0; for(int i = 0;i < size;++i){ if(postorder[postIndex] == inorder[inIndex+i]){ index = inIndex+i; break; }//if }//for int leftSize = index - inIndex; int rightSize = size - leftSize - 1; root->left = InPostBuildTree(inorder,postorder,inIndex,postIndex-1-rightSize,leftSize); root->right = InPostBuildTree(inorder,postorder,index+1,postIndex-1,rightSize); return root; } }; void PreOrder(TreeNode* root){ if(root){ cout<<root->val<<endl; PreOrder(root->left); PreOrder(root->right); }//if } ```

```int main() { Solution solution; vector<int> inorder = {8,4,2,5,1,6,3,7}; vector<int> postorder = {8,4,5,2,6,7,3,1}; TreeNode* root = solution.buildTree(inorder,postorder); PreOrder(root); } ```

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！