题解 | #输出二叉树的右视图#两种思路（建立二叉树再BFS/直接解析二叉树）可通过哈希表进一步优化

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
//     struct TreeNode{
//         int val;
//         TreeNode * left;
//         TreeNode * right;
//     };
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        queue<TreeNode*> q;
        int n = xianxu.size();
//         vector<int> res;
//         TreeNode* root = buildTree(xianxu,zhongxu, 0, n-1, 0, n-1);
//         if(root == NULL) return res;
//         q.push(root);
//         while(!q.empty())
//         {
//             int m = q.size();
//             res.push_back(q.back()->val);
//             for(int i = 0; i < m; i++)
//             {
                
//                 TreeNode* n = q.front();
//                 if(n->left != NULL) q.push(n->left);
//                 if(n->right!= NULL) q.push(n->right);
//                 q.pop();
//             }
            
//         }
        getRightView(xianxu,zhongxu, 0, n-1, 0, n-1,0);
        return res2;
    }
//     TreeNode * buildTree(vector<int>& pre, vector<int>& in, int pre_start, int pre_end, int in_start, int in_end)
//     {
//         if(pre_start > pre_end) return NULL;
//         int key = pre[pre_start];
//         TreeNode* curr = new TreeNode();
//         curr->val = key;
//         int i = in_start;
//         while(in[i] != key) i++;
//         int l_left = i-in_start, l_right = in_end - i;
//         curr->left = buildTree(pre,in,pre_start+1,l_left+pre_start,in_start,i-1);
//         curr->right = buildTree(pre,in,l_left+pre_start+1,pre_end,i+1,in_end);
//         return curr;
//     }
    void getRightView(vector<int>& pre, vector<int>& in, int pre_start, int pre_end, int in_start, int in_end, int level)
    {
        if(pre_start > pre_end) return;
        int key = pre[pre_start];
        if(level == res2.size())
            res2.push_back(key);
        int i = in_start;
        while(in[i] != key) i++;
        int l_left = i-in_start, l_right = in_end - i;
        getRightView(pre,in,l_left+pre_start+1,pre_end,i+1,in_end,level+1);
        getRightView(pre,in,pre_start+1,l_left+pre_start,in_start,i-1,level+1);
    }
private:
    vector<int> res2;
};