题解 | #输出二叉树的右视图#

#include <optional>
#include <variant>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */

    struct Mark {};
    
    using Point = std::vector<int>::const_iterator;
    using Range = std::pair<Point, Point>;
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        auto pt = preOrder.cbegin();
        // NB: 这里需要留足够空间，否则将越界。
        std::vector<std::optional<int>> tree(preOrder.size() * 10, std::nullopt);
        auto tranv = [&pt, &tree](auto&& tranv, Range rg, size_t id) -> void {
            const auto& [l, r] = std::move(rg);
            if(l >= r) {
                return;
            } else {
                tree[id] = *pt;
            }

            auto mid = std::find(l, r, *pt);
            pt ++;
            tranv(tranv, {l, mid}, id << 1);
            tranv(tranv, {mid + 1, r}, (id << 1) | 1);
        };
        tranv(tranv, {inOrder.cbegin(), inOrder.cend()}, 1);
        assert(pt == preOrder.cend());

        std::queue<std::variant<size_t, Mark>> q;
        std::vector<int> res;
        q.emplace(1); q.emplace(Mark{});
        while(not q.empty()) {
            auto cur = q.front(); q.pop();
            if(std::holds_alternative<size_t>(cur)) {
                auto parentId = std::get<size_t>(cur);
                if(std::holds_alternative<Mark>(q.front())) {
                    assert(tree[parentId].has_value());
                    res.push_back(*tree[parentId]);
                }
                if(tree[parentId << 1]) q.emplace(parentId << 1);
                if(tree[(parentId << 1) | 1]) q.emplace((parentId << 1) | 1);
            } else {
                if(not q.empty()) {
                    q.emplace(std::move(cur));
                }
            }
        }
        return res;
    }
};