剑指offer 重建二叉树

可以成功AC。

#include "iostream"
#include "vector"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "cstdlib"
using namespace std;

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

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if( pre.size() == 0 || pre.size() != vin.size())
            return NULL;
        TreeNode* root = new TreeNode(pre[0]);
        if(pre.size() == 1)
            return root;
        int posi = 0;
        for(int i = 0; i < vin.size(); i++)
            if(pre[0] == vin[i]){
                posi = i;
                break;
            }
        if(posi == vin.size())
            return NULL;
        int leftSize = posi;
        root->left = reConstructBinaryTree(vector<int>(pre.begin()+1, pre.begin()+leftSize+1),
                                           vector<int>(vin.begin(), vin.begin()+leftSize));
        root->right = reConstructBinaryTree(vector<int>(pre.begin()+leftSize+1, pre.end()),
                                            vector<int>(vin.begin()+leftSize+1, vin.end()));
        return root;
    }

void preList(TreeNode* root)
{
    if(root){
        cout << root->val << " ";
        preList(root->left);
        preList(root->right);
    }

}

int main()
{
    vector<int> pre;
    vector<int> vin;
    for(int i = 0; i < 8; i++){
        int val;
        cin >> val;
        pre.push_back(val);
    }
    for(int i = 0; i < 8; i++){
        int val;
        cin >> val;
        vin.push_back(val);
    }
    TreeNode* root = reConstructBinaryTree(pre, vin);
    preList(root);
    return 0;
}