LeetCode OJ--Construct Binary Tree from Inorder and Postorder Traversal *
阅读原文时间:2023年07月10日阅读:2

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& inorder, vector& postorder)
{
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 inorder(arr1,arr1+) ;
vector postorder(arr2 ,arr2+);
TreeNode *myNode;

myNode = myS.buildTree(inorder,postorder);

cout<<"hi"<<endl;  
return ;  

}