剑指 Offer：根据前序与中序遍历重建二叉树

二叉树的三种遍历

• 前序：根节点 --> 左子树 --> 右子树
• 中序：左子树 --> 根节点 --> 右子树
• 后序：左子树 --> 右子树 --> 根节点

在前序遍历序列中，从左到右依次取一个数，并找到其在中序遍历中的位置，左边为左子树，右边则是右子树。

按照这种思路，编写代码如下：

TreeNode* helper(vector<int> pre, vector<int> vin, int& k, int l, int r) {
    // k 表示当前是前序序列中的元素的下标，l，r 表示当前中序序列中的左子树或者右子树的边界
    if (k == pre.size()) return nullptr;
    if (l == r) return new TreeNode(vin[l]);
    
    int i = l;
    for (; i <= r; i++) { // 找到根节点的位置
        if (vin[i] == pre[k]) break;
    }
    
    TreeNode* root = new TreeNode(pre[k]);
    
    if (i > l)
        root->left = helper(pre, vin, ++k, l, i - 1); // 进入左子树递归
    if (i < r)
        root->right = helper(pre, vin, ++k, i + 1, r);
    
    return root;
}

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    if (vin.size() != pre.size() || pre.size() == )  ;
     k = ;
    TreeNode* head = (pre, vin, k, , vin.() - );
     head;
}