题解 | #重建二叉树#

题解步骤：

• 1. 如果为空树，返回NULL，同时作为递归调用的出口
• 2. 找出前序遍历的第一个结点，该结点为二叉树的根节点
• 3. 如果只有一个元素，返回结点，也可以作为递归调用出口，可省略
• 4. 找到前序遍历根节点在中序遍历中的位置
• 5. 根据根节点的位置，定义四个容器，分别存放递归调用时候的左子树和右子树
• 6. 进行左子树的递归调用
• 7. 进行右子树的递归调用

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (0 == pre.size() || vin.empty()) 
            return NULL;//空树，也作为递归调用的出口
        //前序遍历，第一个元素即为根节点元素,通过构造函数创建根节点
        TreeNode* root = new TreeNode(pre[0]);
        if (1 == pre.size())//如果只有一个元素，也作为递归调用的出口
            return root;

        int index = 0;//找到根节点在中序遍历中的位置
        for (index;index<vin.size();index++) {
            if (vin[index] == pre[0])//找到中序遍历中根节点的位置
            break;
        }
        //定义四个vector容器，分别存放递归调用时候的pre和vin,
        //下面程序运行后，内存超过限制，放弃
//             vector<int> pre_left;
//             for(int i=0;i<index;i++)//把前序遍历中根节点的左子树放在容器中
//                 pre_left.push_back(pre[i+1]);
//             vector<int> pre_right;
//             for(int i=index;i<pre.size();i++)//把前序遍历中根节点的右子树放在容器中
//                 pre_right.push_back(pre[i+1]);
//             vector<int> vin_left;
//             for(int i=0;i<index;i++)//把中序遍历中根节点的左子树放在容器中
//                 vin_left.push_back(vin[i]);
//             vector<int> vin_right;
//             for(int i=index;i<vin.size();i++)//把前序遍历中根节点的右子树放在容器中
//                 vin_right.push_back(vin[i+1]);
        //使用vector拷贝构造函数分别得到递归调用时需要用到的四个vector区间
        vector<int> pre_left(pre.begin()+1,pre.begin()+index+1);
        vector<int> pre_right(pre.begin()+index+1,pre.end());
        vector<int> vin_left(vin.begin(),vin.begin()+index);
        vector<int> vin_right(vin.begin()+index+1,vin.end());
        //递归构造左右子树
        root->left=reConstructBinaryTree(pre_left, vin_left);
        root->right=reConstructBinaryTree(pre_right, vin_right);
        return root;
    }
};