[wate_baisc]前中序列重构二叉树

中后序列构建二叉树

用了大概6个小时，在递归中止条件没有想好，同时stl没用好end的边界老是越界使用，包括调试的过程中也是越界使用导致调试本身也引发错误（没有debug的CLion啊！！）以后设计end时可以将end单独作为全局的检测元素就不用通过iterator-1来测试（这样本身也是有问题的，如it就是容器第一个！）

#include <vector>
#include <iostream>
using namespace std;
typedef vector<int>::iterator Iterator;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void print(Iterator s, Iterator e){
    while(s != e){
        cout<<*s<<" ";
        s += 1;
    }
}
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return buildTree(pre.begin(), pre.end(), vin.begin(), vin.end());
    }
    TreeNode* buildTree(Iterator pre_beg, Iterator pre_end, Iterator vin_beg, Iterator vin_end){
        TreeNode *t = NULL;
//        cout<<"(";
        if(pre_beg != pre_end) {//一开始是先使用it->val再++it再检测，在end处则直接宕掉
//            print(pre_beg, pre_end);
//            cout<<", ";
//            print(vin_beg, vin_end);
//            cout<<endl;
            t = new TreeNode(*pre_beg);
            ++pre_beg;
            Iterator vin_mid = find(vin_beg, vin_end, *(pre_beg - 1));
            Iterator pre_mid = pre_beg + (vin_mid - vin_beg);
//            cout<<*(pre_mid-1)<<endl;
//            cout<<"pre_mid: "<<*pre_mid<<", pre_end: "<<*(pre_end-1);
//            cout<<", vin_mid+1: "<<*(vin_mid+1)<<", vin_end: "<<*(vin_end-1)<<endl;
//            cout<<"left"<<endl;越界检查，最后一个end总是会出事，而且递归中无法避免，考虑将end和第一个的再前一个两个边界设为全局，然后之间检查每个容器是否为边界；
            t->left = buildTree(pre_beg, pre_mid, vin_beg, vin_mid);
//            cout<<"right"<<endl;
            t->right = buildTree(pre_mid, pre_end, vin_mid + 1, vin_end);
        }
//        else{
//            cout<<"end";
//        }
//        cout<<"), ";
        return t;
    }
};

简洁版

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return buildTree(pre.begin(), pre.end(), vin.begin(), vin.end());
    }
    TreeNode* buildTree(Iterator pre_beg, Iterator pre_end, Iterator vin_beg, Iterator vin_end){
        TreeNode *t = NULL;
        if(pre_beg != pre_end) {
            t = new TreeNode(*pre_beg);
            ++pre_beg;
            Iterator vin_mid = find(vin_beg, vin_end, *(pre_beg - 1));
            Iterator pre_mid = pre_beg + (vin_mid - vin_beg);
            t->left = buildTree(pre_beg, pre_mid, vin_beg, vin_mid);
            t->right = buildTree(pre_mid, pre_end, vin_mid + 1, vin_end);
        }
        return t;
    }
};

时间O（n），空间O（n）