构造二叉树可以通过 前序+中序 、后序+中序两种方法。

这两种方法的核心思路都是 通过前/后序确定二叉树的根节点，然后在中序中根据根节点进行划分。然后递归。

 

前序+中序

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return BuildTree(0,pre.size()-1,0,vin.size()-1,pre,vin);
    }
    TreeNode* BuildTree(int leftpre,int rightpre,int leftin,int rightin,vector<int> pre,vector<int> vin){
        if(leftin>rightin)return NULL;
        TreeNode* root=new TreeNode(pre[leftpre]);
        int rootin=leftin;
        while(rootin<=rightin&&pre[leftpre]!=vin[rootin])rootin++;
        int left=rootin-leftin;
        root->left=BuildTree(leftpre+1,leftpre+1+left-1,leftin,rootin-1,pre,vin);
        root->right=BuildTree(leftpre+left+1,rightpre,rootin+1,rightin,pre,vin);
        return root;
    }
};

 

后序+中序（引用leetcode“宝宝可乖了”）