leetcode-106. 中間シーケンスと後シーケンスからシーケンスを遍歴してツリーを構築する
1435 ワード
詳しくは別のブログを参照してください.
https://blog.csdn.net/u014450222/article/details/80889403
1本の木の中順遍歴と後順遍歴に基づいて二叉樹を構築する.
注意:ツリーに重複する要素がないと仮定できます.
たとえば、
次のツリーを返します.
https://blog.csdn.net/u014450222/article/details/80889403
1本の木の中順遍歴と後順遍歴に基づいて二叉樹を構築する.
注意:ツリーに重複する要素がないと仮定できます.
たとえば、
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
次のツリーを返します.
3
/ \
9 20
/ \
15 7
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int SearchInt(vector inorder,int val)
{
for(int i=0;i& inorder, vector& postorder) {
int n=inorder.size();
if(n>0)
{
TreeNode *root=new TreeNode(postorder[n-1]);//
int mid=SearchInt(inorder,root->val);
vector a,b,c,d;//
a.assign(inorder.begin(),inorder.begin()+mid);// :vector assign
b.assign(postorder.begin(),postorder.begin()+mid);
c.assign(inorder.begin()+mid+1,inorder.end());
d.assign(postorder.begin()+mid,postorder.end()-1);
root->left=buildTree(a,b);//
root->right=buildTree(c,d);//
return root;
}
else
return nullptr;
}
};