http://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
知道二叉树的中序遍历和后序遍历序列,求二叉树。
使用递归
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution{
public:
TreeNode* buildTree(vector
{
return buildTree(begin(inorder),end(inorder),begin(postorder),end(postorder));
}
template
TreeNode* buildTree(BidiIt in_first, BidiIt in_last,BidiIt post_first,BidiIt post_last)
{
if(in_first ==in_last)
return nullptr;
if(post_first == post_last)
return nullptr;
const auto val = *prev(post_last);
TreeNode* root = new TreeNode(val);
auto in\_root\_pos = find(in\_first,in\_last,val);
auto left\_size = distance(in\_first,in\_root\_pos);
auto post\_left\_last = next(post\_first,left\_size);
root->left = buildTree(in\_first,in\_root\_pos,post\_first,post\_left\_last);
root->right = buildTree(next(in\_root\_pos),in\_last,post\_left\_last,prev(post\_last));
return root;
}
};
int main()
{
Solution myS;
int arr1[] = {,};//,5,1,6,3,7 };
int arr2[] = {,};//,2,6,7,3,1 };
vector
vector
TreeNode *myNode;
myNode = myS.buildTree(inorder,postorder);
cout<<"hi"<<endl;
return ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章