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

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */

    
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        if (xianxu.empty() || zhongxu.empty()) return {};
        map<int, int> zx_map;
        for(int i=0; i<zhongxu.size();i++){
            zx_map[zhongxu[i]] = i;
        }
        int n = xianxu.size();
        vector<int> ret;
        queue<int> que;
        que.push(0);
        int pre_z_idx = n;
        set<int> del_idx;
        while (!que.empty()){
            int sz = que.size();
            while (sz--){
                int idx = que.front();
                int val = xianxu[idx];
                que.pop();
                if (sz == 0){
                    ret.push_back(val);
                }
                int z_idx = zx_map[val];
                if (idx+1<n && zx_map[xianxu[idx+1]] < z_idx){
                    del_idx.insert(xianxu[idx+1]);
                    que.push(idx+1);
                }
                for (int j=idx+1; j<n; j++){
                    if (zx_map[xianxu[j]] > z_idx){
                        if (del_idx.find(xianxu[j]) != del_idx.end()) break;
                        del_idx.insert(xianxu[j]);
                        que.push(j);
                        break;
                    }
                }
            }
             
        }
        return ret;
        
    }
};

直接通过前序和中序遍历结果，进行层序遍历，每一层最右边的值返回