[剑指offer][04]重建二叉树

题目描述：

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

解题思路：

根据前序的第一个数字pre[0]是根的特性，再在中序中找到pre[0]在中序中的索引idx，分开，左边的是左子树，右边的是右子树。然后递归求出结果。

代码实现

思路1：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //递归终止条件
        if(!pre.size()){
            return nullptr;
        }
        
        vector<int> lef_pre,lef_vin;
        vector<int> rig_pre,rig_vin;
        TreeNode *head=new TreeNode(pre[0]);
        //找到根节点
        size_t idx=-1;
        for(size_t i=0;i<vin.size();i++)
        {
            if(vin[i]==pre[0]){
                idx=i;
                break;
            }    
        } 
        if(idx == -1){
            return nullptr;
        }
        //树的根节点
        head->val = vin[idx];
        //左子树的前序中序       
        for(size_t i=0;i<idx;i++){
            lef_pre.push_back(pre.at(i+1));
            lef_vin.push_back(vin.at(i));
        }
        //右子树的前序中序
        for(size_t i=idx+1;i<pre.size();i++){
            rig_pre.push_back(pre.at(i));
            rig_vin.push_back(vin.at(i));
        }
        //递归重建树的左右子树 
        head->left=reConstructBinaryTree(lef_pre,lef_vin);
        head->right=reConstructBinaryTree(rig_pre,rig_vin);
        return head;
    }
};

参考链接

剑指Offer——重建二叉树——C++