题解 | #重建二叉树#

1. 与树有关的问题第一时间尝试递归，分解子问题。
2. 前序遍历的顺序是中左右，所以如果利用遍历结果建树，那么前序遍历数组的第一个数一定是根节点存储的树。
3. 在中序遍历数组中找到这个根节点存储的数，因为中序遍历的顺序是左中右，所以中序遍历数组中该数左边的部分一定是根节点左子树存储的数，该数右边的部分一定是根节点右子树存储的数。
4. 因为知道了中序遍历数组的左边界、右边界和根节点所在的下标，所以可以求出左子树、右子树的中序遍历数组长度，根据这些长度可以同样划分前序遍历数组。
5. 利用划分出来的左右子树的前序遍历、中序遍历数组，对左子树和右子树递归建树，最后将指针赋值给根节点的左右子树指针，返回根节点即可。

class Solution {
public:
    TreeNode* reConstructBinaryTree2(vector<int>& pre,vector<int>& vin, int pl, int pr, int vl, int vr) {
        if (pl > pr) return nullptr;
        if (pl == pr) return new TreeNode(pre[pl]);
        TreeNode* res = new TreeNode(pre[pl]);
        int vm = vl;
        for (; vm <= vr; vm++) {
            if (vin[vm] == pre[pl]) break;
        }
        res->left = reConstructBinaryTree2(pre, vin, pl + 1, pl + vm - vl, vl, vm - 1);
        res->right = reConstructBinaryTree2(pre, vin, pl + vm - vl + 1, pr, vm + 1, vr);
        return res;
    }

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return reConstructBinaryTree2(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
    }
};