根据前序遍历和中序遍历构建二叉树

采用先序遍历的思想构建即可。

编码过程中，遇到了一个bug，只能通过25%的样例，反复检查逻辑问题，没有什么差错，最后面发现，原来是把第36行的==写成了=2333。总结：定位bug需要从多方面考虑：

1. 如果是样例通过不了：考虑算法思路是否有误、运算符是不是写错了
2. 如果是编译错误：考虑语法问题
3. 如果是段错误、溢出：考虑边界问题，尤其是指针和数组下标

//
// Created by jt on 2020/8/21.
//
#include <vector>
using namespace std;


struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val): val(val), left(0), right(0) {}
};


class Solution {
public:
    /**
     *
     * @param preorder int整型vector
     * @param inorder int整型vector
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // write code here
        int size = preorder.size();
        return inOrder(preorder, 0, size - 1, inorder, 0, size -1);
    }

    TreeNode* inOrder(vector<int> &preorder, int pL, int pR,
                      vector<int> &inorder, int iL, int iR) {
        if (pL > pR) return nullptr;
        TreeNode *root = new TreeNode(preorder[pL]);
        int mid = iL;
        for (; mid <= iR; ++mid)
            if (inorder[mid] == root->val) break;
        int sizeLeft = mid - iL;
        // 中左右 左中右
        root->left = inOrder(preorder, pL+1, pL+sizeLeft, inorder, iL, mid-1);
        root->right = inOrder(preorder, pL+sizeLeft+1, pR, inorder, mid+1, iR);
        return root;
    }
};