04：重建二叉树

题目描述

• 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

• 根据前序和中序的特点， 前序的第一个元素，这个树的根节点，在中序中找到这个元素，这个数左边的所有节点，是这个节点的左子树节点，这个数右边的节点是，这个节点的右子树节点。按照这个规律递归构建整个数。

AC代码

class Solution {
public:  
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0)
            return nullptr;
        
        int head = pre.at(0);
        TreeNode * node = new TreeNode(head);
        
        auto iter = find(vin.begin(), vin.end(), head);
        auto dis = iter - vin.begin();
        
        node->left = reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + 1 + dis),
                                           vector<int>(vin.begin(), iter));
                                          
        node->right= reConstructBinaryTree(vector<int>(pre.begin() + 1 + dis, pre.end()),
                                           vector<int>(iter + 1 , vin.end()));
                                          
        return node;
    }
};