题意整理：

题目给出一颗二叉树的前序遍历以及中序遍历，要求得到这颗二叉树的右视图。右视图简单的理解，既在树的右侧能够看到的数的第一个元素。更专业的说，即为树的每一层的最右侧元素。

方法一：递归+层序遍历

核心思想：

可以先使用递归，从先序遍历和中序遍历中重构树，再使用层次遍历求出右视图。
重构树：对一颗二叉树，其前序遍历的顺序为：
1.遍历根节点 2.递归地遍历左子树 3.递归地遍历右子树。
其中序遍历的顺序为：
1.递归地遍历左子树. 2遍历根节点 3.递归地遍历右子树。
在递归遍历子树的过程中，可以将这颗子树看成一颗新的树按以上步骤进行重建，所以重构可以通过简单的的递归实现。
对于前序遍历，其第一个元素就是根节点，故只要在中序遍历中定位到根节点，就可以知道左子树和右子树中的节点数目。而同一颗子树的前序遍历和中序遍历的长度相同，所以将此结果对应到前序遍历上，就可以对数组进行划分后递归，得到最终结果
图示：
层序遍历得到右视图：将树重建之后，只需要对数进行层序遍历，每次取出一整层且记录每层最后一个元素，遍历完成后便得到结果。层序遍历可以借助队列实现。

核心代码：

class Solution {
public:
    //构建的树的结构
    struct Node{
        int val;
        Node* left;
        Node* right;
        Node() : val(0), left(nullptr), right(nullptr) {}
        Node(int x) : val(x), left(nullptr), right(nullptr) {}
    };
    //建树函数
    Node* build(vector<int>& xianxu, vector<int>& zhongxu, int L1, int R1, int L2, int R2) {
        if(L1 > R1 || L2 > R2) return nullptr;
        int val = xianxu[L1];//以前序遍历的第一个元素为根
        int p = L2;
        while(zhongxu[p] != val) ++p;//寻找中序遍历中根节点位置
        int jump = p - L2;
        Node* root = new Node(val);
        //递归建立左右子树
        root->left = build(xianxu, zhongxu, L1 + 1, L1 + jump, L2, p - 1);
        root->right = build(xianxu, zhongxu, L1 + jump + 1, R1, p + 1, R2);
        return root;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        Node* root = build(xianxu, zhongxu, 0, xianxu.size() - 1, 0, zhongxu.size() - 1);
        vector<int> ans;
        if(root == nullptr) {
            return ans;
        }
        //层序遍历得到右视图
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            int n = q.size(); //当前层的长度
            for(int i = 0; i < n; ++i) {
                Node* t = q.front(); 
                q.pop();
                if(i == n - 1) ans.push_back(t->val);//每一层最后一个节点
                if(t->left != nullptr) q.push(t->left);
                if(t->right != nullptr) q.push(t->right);
            }
        }
        return ans;
    }

复杂度分析：

时间复杂度：, 是树的节点数。建树时，最坏情况的树为左偏树，此时每次遍历都需要找到最右边找到中序遍历的根节点，进行 次遍历，故复杂度为 。层序遍历时每个节点最多访问一次，复杂度为
空间复杂度：，既当树退化为链表时所需的栈空间，以及层序遍历时的队列空间，两者都不会超过树的节点数 。

方法二：在递归中直接得到右视图

核心思想：

题目要求的只是返回右视图，所以可以考虑不对二叉树进行实际的重建。
同方法一，在通过找到前序遍历的首元素在中序遍历中的位置进行递归时，可以在递归时同时记录本节点处于的高度，如果高度不存在于答案数组，进行填入；否则说明本节点比答案数组中的同高度节点位于同一层且更靠右，可以进行更新。（因为递归是先左子树后右子树，保证了后遍历到的同高度节点是靠右侧的节点）

核心代码：

class Solution {
public:
    vector<int> ans;//存储答案

    void find(vector<int>& xianxu, vector<int>& zhongxu, int L1, int R1, int L2, int R2, int height) {
        if(L1 > R1 || L2 > R2) return;
        int val = xianxu[L1];//以先序遍历的第一个元素为根
        int p = L2;
        while(zhongxu[p] != val) ++p;//寻找中序遍历中根节点位置
        int jump = p - L2;
        if(height > ans.size()) {
            ans.push_back(val);
        } else {
            ans[height - 1] = val;//更新最新的最右节点
        }
        //递归寻找左右子树
        find(xianxu, zhongxu, L1 + 1, L1 + jump, L2, p - 1, height + 1);
        find(xianxu, zhongxu, L1 + jump + 1, R1, p + 1, R2, height + 1);
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        find(xianxu, zhongxu, 0, xianxu.size() - 1, 0, zhongxu.size() - 1, 1);
        return ans;
    }
};

复杂度分析：

时间复杂度：, 是树的节点数。同方法一，当最坏情况时，树为左偏树，此时每次遍历都需要找到最右边找到中序遍历的根节点，进行 次遍历，故复杂度为 。
空间复杂度：，既当树退化为链表时所需的栈空间。