面试题7：重建二叉树（c++）【剑指 offer】

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} //可用于初始化
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int m=pre.size(),n=vin.size();
        if(m!=n||m==0) return NULL;
        return reconstruct(pre,vin,0,m-1,0,n-1);
    }
    TreeNode* reconstruct(vector<int> &pre,vector<int> &vin,int l1,int r1,int l2,int r2){
            TreeNode* root=new TreeNode(pre[l1]); //创建根节点，并初始化。利用树节点的定义初始化。
            if(l1==r1) return root; //如果只有一个节点则返回该节点，也就是根节点
            int indexnum=l2; //indexnum用来表示根节点在中序遍历数组vin中的索引数字，即位置。初始值设置为l2
            while(indexnum<=r2&&pre[l1]!=vin[indexnum]) indexnum++; //遍历数组vin，找根节点在中序遍历中的位置
            int leftlength=indexnum-l2; //根节点的左子树的节点个数
            int rightlength=r2-indexnum; //根节点的右子树的节点个数
            if(leftlength>0){ //左子树有节点时，递归构造左子树
                root->left=reconstruct(pre,vin,l1+1,l1+leftlength,l2,indexnum-1);
            }
            if(rightlength>0){ //右子树有节点时，递归构造右子树
                root->right=reconstruct(pre,vin,l1+leftlength+1,r1,indexnum+1,r2);
            }
            return root; //返回根节点
    }
};