題目
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
* 網(wǎng)址：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
* 結(jié)果：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
// 根節(jié)點(diǎn)
TreeNode* root = new TreeNode(postorder[postIndex]);
// 尋覓postorder[postIndex]在中序序列中的下標(biāo)
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);
}
運(yùn)行時間
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
