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

在重建树的同时进行右视图填充
1.重建树的过程就是根据先序结果找到子树根节点，根据中序结果划分左右子树；以此递归；
2.右视图即每一层最右边的节点（每层只有一个节点会入结果集），我们只需在重建树的过程中用一个变量n表示当前层数（从1开始），并以先右后左的顺序进行递归；那么当目前右视图结果集中元素数量小于当前层数时，就把当前节点值写入结果集。

class Solution {
public:
    vector<int> ans;
    //left1表示先序遍历找到的当前根节点；left2与righ2为中序遍历中当前子树区间；
    //n为当前遍历的层数（第i层，从1开始）
    void dfs(vector<int>& xianxu, vector<int>& zhongxu,int left1,int left2,int right2,int n)   
    {
        if(left2==right2)
            return;
        if(ans.size()<n)     //结果集中元素数少于层数，说明此时该层还未压入节点
            ans.emplace_back(xianxu[left1]);
        int newleft1=0;
        for(int i=left2;i<right2;++i)
        {
            if(zhongxu[i]==xianxu[left1])
            {
                newleft1=i;
                break;
            }
        }
        //先右后左递归，保证每次入结果集的为最右侧的节点
        dfs(xianxu,zhongxu,left1+newleft1-left2+1,newleft1+1,right2,n+1);   
        dfs(xianxu,zhongxu,left1+1,left2,newleft1,n+1);
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        dfs(xianxu,zhongxu,0,0,xianxu.size(),1);
        return ans;
    }
};