[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.

思路

思路和[LeetCode]*105.Construct Binary Tree from Preorder and Inorder Traversal1样。

代码

/*---------------------------------------
* 日期: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);
}

运行时间

这里写图片描述

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

波比源码 » [LeetCode]*106.Construct Binary Tree from Inorder and Postorder Traversal

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡