题解 | 树的子结构

• if（pre[left]==mid[tag]） 则
• 找到了根的位置(left是当前树范围终pre第一个元素)
• mid的起始位置到j-1为左子树数组范围，j+1到mid的终止位置为右子树的数组范围
• pre的起始位置+1到pre+左子树大小为左子树的范围，pre+左子树大小+1到pre的终止位置为右子树范围。

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

*/
class Solution {
int left,right;
public:
    TreeNode* build(vector<int>&pre,vector<int>& vin,int left1,int right1,int left2,int right2){
        if(left>right||right2>right||left1>right1||left2>right2) return NULL;
        int num=pre[left1];
        TreeNode *head=new TreeNode(num);
        vector<int>::iterator iter=find(vin.begin(), vin.end(),num);
        int pos=iter-vin.begin();
        head->left=build(pre, vin, left1+1, left1+pos-left2, left2, pos-1);
        head->right=build(pre, vin, left1+1+pos-left2,right1, pos+1, right2);
        return head;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        left=0;
        right=pre.size()-1;
        return build(pre,vin, left,  right,  left,  right);
    }
};