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

// 构造二叉树 + 层次遍历


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
       TreeNode *root= makeTree(xianxu,0, xianxu.size()-1, zhongxu, 0, zhongxu.size()-1);
       // bfs
       vector<int> ans;
       queue<TreeNode*> qu;
       qu.push(root);
       while(!qu.empty()){
           int size=qu.size();
           while(size--){
               TreeNode *p=qu.front();
               qu.pop();
               if(size==0) ans.push_back(p->val);
               if(p->left) qu.push(p->left);
               if(p->right) qu.push(p->right);
           }
       }
       return ans;
    }


private:
    TreeNode* makeTree(vector<int>& xianxu, int xl,int xr,vector<int>& zhongxu,int zl,int zr){
        if(xl>xr || zl > zr) return NULL;
        TreeNode *root=new TreeNode(xianxu[xl]);
        int mid=0;
        for(int i=0;i<zhongxu.size();i++){
            if(zhongxu[i]==xianxu[xl]){
                mid=i;
                break;
            }
        }

        root->left=makeTree(xianxu, xl+1 , xl+mid-zl ,zhongxu, zl , mid-1 );
        root->right=makeTree(xianxu, xl+mid-zl+1, xr, zhongxu, mid+1, zr);
        return root;
    }
};