C/C++实现：根据遍历序列递归创建二叉树

struct BitTree {
  int val;
  BitTree* left;
  BitTree* right;
  BitTree(int x) : val(x), left(NULL), right(NULL) {}
};

BitTree* create1(vector<int>& pre, int x1, int x2, int x3, int x4) {
  if(x1 > x2 || x3 > x4) {
    return NULL;
  }
  //创建根结点 
  int root_val = pre[x1];
  BitTree* root = new BitTree(root_val);
  int x = mp[root_val];  //中序遍历中根的位置
  int y = x - x3 + x1;
  //创建左子树
  root->left = create1(pre, x1 + 1, y, x3, x - 1);
  //创建右子树 
  root->right = create1(pre, y + 1, x2, x + 1, x4);
  return root; 
}

BitTree* create2(vector<int>& post, int x1, int x2, int x3, int x4) {
  if(x1 > x2 || x3 > x4) {
    return NULL;
  }
  //创建根结点
  int root_val = post[x2];
  BitTree* root = new BitTree(root_val);
  int x = mp[root_val]; //中序遍历中的位置
  int y = x1 + x - 1 - x3;
  //创建左子树
  root->left = create2(post, x1, y, x3, x - 1);
  //创建右子树
  root->right = create2(post, y + 1, x2 - 1, x + 1, x4);
  return root; 
}

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
using namespace std;

map<int, int> mp;

struct BitTree {
  int val;
  BitTree* left;
  BitTree* right;
  BitTree(int x) : val(x), left(NULL), right(NULL) {}
};

BitTree* create1(vector<int>& pre, int x1, int x2, int x3, int x4) {
  if(x1 > x2 || x3 > x4) {
    return NULL;
  }
  //创建根结点 
  int root_val = pre[x1];
  BitTree* root = new BitTree(root_val);
  int x = mp[root_val];  //中序遍历中根的位置
  int y = x - x3 + x1;
  //创建左子树
  root->left = create1(pre, x1 + 1, y, x3, x - 1);
  //创建右子树 
  root->right = create1(pre, y + 1, x2, x + 1, x4);
  return root; 
}

//中序遍历和后续遍历构建二叉树
BitTree* create2(vector<int>& post, int x1, int x2, int x3, int x4) {
  if(x1 > x2 || x3 > x4) {
    return NULL;
  }
  //创建根结点
  int root_val = post[x2];
  BitTree* root = new BitTree(root_val);
  int x = mp[root_val]; //中序遍历中的位置
  int y = x1 + x - 1 - x3;
  //创建左子树
  root->left = create2(post, x1, y, x3, x - 1);
  //创建右子树
  root->right = create2(post, y + 1, x2 - 1, x + 1, x4);
  return root; 
}

//层次遍历
void level(BitTree* T) {
  queue<BitTree*> que;
  que.push(T);
  while(!que.empty()) {
    BitTree* t = que.front();
    que.pop();
    cout << t->val << " ";
    if(t->left) {
      que.push(t->left);
    }
    if(t->right) {
      que.push(t->right);
    }
  }
}

void post_order(BitTree* T) {
  if(T) {
    post_order(T->left);
    post_order(T->right);
    cout << T->val << " ";
  }
}

int main() {
  vector<int> pre = {3, 9, 20, 15, 7};
  vector<int> in = {9, 3, 15, 20, 7};
  vector<int> post = {9, 15, 7, 20, 3};
  for(int i = 0; i < in.size(); i++) {
    mp[in[i]] = i;  //记录中序遍历中元素的位置
  }
  int size = in.size();
  BitTree *T1 = create1(pre, 0, size - 1, 0, size - 1);
  BitTree *T2 = create2(post, 0, size - 1, 0, size - 1);
  post_order(T1);
  cout << endl;
  post_order(T2);
  return 0;
}