[LeetCode]*106.Construct Binary Tree from Inorder and Postor
发布时间：2020-12-13 20:44:08 所属栏目：PHP教程 来源：网络整理
导读：题目 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样。 代码 /*
|
题目 Given inorder and postorder traversal of a tree,construct the binary tree. Note: 思路 思路和[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,inIndex,postIndex-1-rightSize,leftSize);
root->right = InPostBuildTree(inorder,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,7,1};
TreeNode* root = solution.buildTree(inorder,postorder);
PreOrder(root);
}
运行时间
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
