【牛客题霸题解】输出二叉树的右视图（待更新java、py）

前置题目：
NC12 重建二叉树
NC15 求二叉树的层序遍历
先根据前序和中序把二叉树重建出来，然后获取每一层的最右结点就可以了

class Solution {
public:
    struct TreeNode{
        int val;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
        TreeNode* left;
        TreeNode* right;
    };
    void Build(TreeNode* &root,vector<int> &pre,vector<int> &vin,int ps,int is,int len)
    {
        if(len == 0){root = NULL;return;}
        int Root = pre[ps];
        root = new TreeNode(Root);
        int Lnum = 0;
        int Rnum = 0;
        for(int i = 0 ; i < len ; i++)
        {
            if(vin[is+i] != Root)
            {
                Lnum++;
            }
            else{
                break;
            }
        }
        Rnum = len-Lnum-1;
        Build(root->left,pre,vin,ps+1,is,Lnum);
        Build(root->right,pre,vin,ps+1+Lnum,is+1+Lnum,Rnum);
    }
    TreeNode* root = NULL;
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        Build(root,xianxu,zhongxu,0,0,zhongxu.size());
        vector<vector<int> > ans;
        queue< pair<TreeNode*,int> > Q;
        Q.push(pair<TreeNode*,int> (root,0));
        while(!Q.empty())
        {
            TreeNode* now = Q.front().first;
            int cur = Q.front().second;
            Q.pop();
            if(now == NULL){continue;}
            vector<int> temp;
            if(cur+1 >ans.size())
            {
                ans.push_back(temp);
            }
            ans[cur].push_back(now->val);
            if(now->left != NULL){
                Q.push(pair<TreeNode*,int>(now->left,cur+1));
            }
            if(now->right != NULL){
                Q.push(pair<TreeNode*,int>(now->right,cur+1));
            }
        }
        vector<int> Right;
        for(int i = 0 ;i < ans.size() ; i ++)
        {
            Right.push_back(ans[i][ans[i].size()-1]);
        }
        return Right;
    }
};