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

先建树，再层次遍历。根据前序遍历和中序遍历建树，递归左前序左中序，递归右前序右中序；通过队列层次遍历，并保存每一层的最后一个元素。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* pre_in(vector<int>& pre_order,vector<int>& in_order){
        if(pre_order.empty()) return nullptr;
        TreeNode* root=new TreeNode{pre_order[0]};
        int pos=0;
        for(;pos<in_order.size();pos++){
            if(in_order[pos]==pre_order[0]) break;
        }
        vector<int> left_pre{};
        vector<int> right_pre{};
        for(int i=1;i<pre_order.size();i++){
            if(i<=pos) left_pre.push_back(pre_order[i]);
            else right_pre.push_back(pre_order[i]);
        }
        vector<int> left_in{};
        vector<int> right_in{};
        for(int i=0;i<in_order.size();i++){
            if(i<pos) left_in.push_back(in_order[i]);
            else if(i>pos) right_in.push_back(in_order[i]);
        }
        root->left=pre_in(left_pre,left_in);
        root->right=pre_in(right_pre,right_in);
        return root;
    }
    
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        TreeNode* root=pre_in(xianxu, zhongxu);
        vector<int> result{};
        if(root==nullptr) return result;
        queue<TreeNode*> que{};
        que.push(root);
        while(!que.empty()){
            int n=que.size();
            for(int i=0;i<n;i++){
                TreeNode* node=que.front();
                que.pop();
                if(i==n-1){
                    result.push_back(node->val);
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result;
    }
};