题解 | #输出二叉树的右视图#（递归建立二叉树&二叉树数层次遍历）

class Solution {
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        TreeNode* res = build(xianxu, 0, xianxu.size()-1,zhongxu, 0, zhongxu.size()-1); // 建立二叉树
        queue<TreeNode *> q; // 层次遍历
        q.push(res);
        vector<int> ans;
        while(!q.empty()){
            int size = q.size(); //当前层队列元素个数
            while(size--){
                TreeNode *tmp = q.front();  q.pop();
                if(size == 0)ans.push_back(tmp->val);  //当前层最后一个元素加入ans，即右视图
                if(tmp->left)q.push(tmp->left); // 下一层元素入队
                if(tmp->right)q.push(tmp->right);
            }
        }
        return ans;
    }

    TreeNode* build(vector<int>& xianxu,int l1,int r1, vector<int>& zhongxu, int l2, int r2){
        int k;
        for(k = l2; k <= r2; k++){
            if(zhongxu[k] == xianxu[l1]) break; // 先序第一个在中序中的结点位置
        }
        if(k > r2) return NULL; // 没找到返回空
        TreeNode * res = new TreeNode(xianxu[l1]); // 个根节点
        res->left = build(xianxu, l1+1,l1+k-l2,zhongxu,l2,k-1); // 根节点左子树
        res->right = build(xianxu, l1+k-l2+1, r1, zhongxu, k+1, r2); // 右子树
        return res;
    }
};