제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 재건하십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* reConstructBinaryTree(vector pre, vector vin)
{
int pre_len = pre.size();
int in_len = vin.size();
if(pre_len == 0 || in_len == 0 || pre_len != in_len)
return NULL;
TreeNode *head = new TreeNode(pre[0]);//
int root_ind = 0;// root
for(int i = 0; i in_left, in_right,pre_left, pre_right;
for(int j = 0; jright = reConstructBinaryTree(pre_right, in_right);
head->left = reConstructBinaryTree(pre_left, in_left);
return head;
}
// ,
void inorderTraverseRecursive(TreeNode *root)
{
if(root != NULL){
inorderTraverseRecursive(root->left);
cout<val<right);
}
}
int main(){
int pre[] = {1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
vector pre_vec(pre, pre+8);
vector in_vec(std::begin(in), std::end(in));
// for(auto item: pre_vec)
// cout<