题解 | #重建二叉树#

/**
 * 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类
     */
    std::vector<std::unique_ptr<TreeNode>> pool;
    using Point = std::vector<int>::const_iterator;
    using Range = std::pair<Point, Point>;
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        std::vector<std::unique_ptr<TreeNode>> pool;
        auto pt = preOrder.begin();
        auto rebuild = [&pool, &pt](auto&& rb, Range rg) -> TreeNode* {
            const auto& [l, r] = std::move(rg);
            if(l >= r) return nullptr;
            auto node = pool.emplace_back(std::make_unique<TreeNode>(*pt)).get();
            auto mid = std::find(l, r, *pt);
            pt ++;
            node->left = rb(rb, {l, mid});
            node->right = rb(rb, {mid + 1, r});
            return node;
        };
        auto root = rebuild(rebuild, {vinOrder.cbegin(), vinOrder.cend()});
        this->pool = std::move(pool);
        return root;
    }
};