题解 | #重建二叉树#

解题思路：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但是在树的中序遍历中，根节点的值在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树的节点的值位于根节点的值的右边。因此根据先序遍历第一个值为根节点的值，扫描中序遍历，找到根节点的值的位置，位于根节点位置的左边的是左子树的节点，位于根节点位置右边的是右子树的节点。在扫描完之后，我们分别找到了左右子树先序和中序的遍历，我们就可以用同样的方法分别构建左子树和右子树，接下来的事情可以用递归来实现。

时间复杂度：O(n)，在遍历的过程都是O(n)的数量级；

空间复杂度：O(n)，递归使用的栈的最大深度不超过n;

基于C++实现：

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //当前序或者中序遍历为空的情况
        if(pre.empty() || vin.empty()){
            return nullptr;
        }
        //建立根节点
        int root = pre[0];
        TreeNode *tree = new TreeNode(root);
        int length = pre.size();
        //如果长度为1，直接返回根节点
        if(length == 1){
            return tree;
        }
        auto posi = find(vin.begin(), vin.end(), root);
        //如果在中序中没有检测到根节点
        if(posi == vin.end()){
            return nullptr;
        }
        //计算左右子树的长度
        int num_left = posi - vin.begin();
        int num_right = vin.end() - posi - 1;
        vector<int> left_pre;
        vector<int> left_vin;
        vector<int> right_pre;
        vector<int> right_vin;
        //找左右子树对应的先序和中序遍历
        left_pre.assign(pre.begin()+1, pre.begin()+1+num_left);
        right_pre.assign(pre.end()-num_right, pre.end());
        left_vin.assign(vin.begin(), vin.begin()+num_left);
        right_vin.assign(vin.end()-num_right, vin.end());
        //递归的建立左右子树
        tree->left = reConstructBinaryTree(left_pre, left_vin);
        tree->right = reConstructBinaryTree(right_pre, right_vin);
        return tree;
    }
};