重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：

思路比较直白，由前序遍历可得根节点，然后由中序遍历得左右子树。左右子树重复这个过程。即递归。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //找到目标数的下标
    int helpIndex(vector<int>& nums,int start,int end,int target) {
        int n = nums.size();
        for(int i = start;i <= end;i++) {
            if(nums[i] == target) {
                return i;
            }
        }
        return 0;
    }
    //递归函数，重建二叉树
    TreeNode* helper(vector<int>& pre,int start,int end,vector<int>& vin,int startvin,int endvin){

        if(start > end || startvin > endvin) return nullptr;
        TreeNode* root = new TreeNode(pre[start]);
        //递归出口，叶子结点
        if(start == end) {
            return root;
        }
        //找出根节点所在位置
        int mid = helpIndex(vin,startvin,endvin,pre[start]);
        //重建左子树
        root->left = helper(pre, start+1, start+(mid-startvin), vin, startvin, mid - 1);
        //重建右子树
        root->right = helper(pre, start+(mid-startvin)+1, end, vin, mid+1, endvin);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        int n = preorder.size();
        return helper(preorder, 0, n-1, inorder, 0, n-1);
    }
};