题解 | #重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        // 参考思路：前序遍历，第一个确定的是根节点；中序遍历，确定左子树、右子树；递归更新左右子树
        if(preOrder.empty()) return nullptr;
        // 前序遍历第一个是根节点
        TreeNode* root = new TreeNode(preOrder.front());
        // 根据中序遍历确定左右子树，获取标记位置迭代器
        vector<int>::iterator root_vin = find(vinOrder.begin(), vinOrder.end(), root->val);
        // 根据中序遍历所获取的迭代器位置，获取前序遍历时区分左右子树
        int id = root_vin - vinOrder.begin();
        // std::cout << id << std::endl;

        // 左右子树迭代更新: 参数一：前序遍历， 参数二：中序遍历
        vector<int> preOrder_left(preOrder.begin()+1, preOrder.begin()+id+1);   // 划分前序遍历的左子树
        vector<int> preOrder_right(preOrder.begin()+1+id, preOrder.end());      // 划分前序遍历的右子树
        vector<int> vinOrder_left(vinOrder.begin(), root_vin);                  // 划分中序遍历的左子树
        vector<int> vinOrder_right(root_vin+1, vinOrder.end());                 // 划分中序遍历的右子树
        // for(auto i : vinOrder_right)
        //     std::cout << i << " ";
        root->left = reConstructBinaryTree(preOrder_left, vinOrder_left);
        root->right = reConstructBinaryTree(preOrder_right, vinOrder_right);
        
        return root;
    }
};