首页 > 代码库 > [leetcode] Construct binary tree from inorder and postorder traversal
[leetcode] 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.
postorder 为左 右 中，所以postorder的最后一个为根，取得树根后，在inorder中可以找到左子树与右子树的元素。
问题可分解为，找根，确定左子树与右子树的元素。所以，递归求解。
由于，postorder是从左至右存储根节点的，所以要先构造右子树。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int postindex;
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.size()==0||postorder.size()==0)
return NULL;
postindex=postorder.size()-1;
int stat=0;
int end=postorder.size()-1;
return foo(inorder,postorder,stat,end);
}
TreeNode* foo(vector<int> &inorder,vector<int> &postorder,int stat,int end){
if(stat>end)
return NULL;
TreeNode* root=new TreeNode(0);
root->val=postorder[postindex];
postindex=postindex-1;
int indexOfRoot=index(inorder,root->val);
if(indexOfRoot==-1)
exit(0);
if(stat==end)
return root;
root->right=foo(inorder,postorder,indexOfRoot+1,end);
root->left=foo(inorder,postorder,stat,indexOfRoot-1);
return root;
}
int index(vector<int> v,int val){
int i;
for(i=0;i<v.size();i++)
if(v[i]==val)
return i;
return -1;
}
};[leetcode] Construct binary tree from inorder and postorder traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。