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

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        vector<int>v;
        int n=xianxu.size();
        int m=zhongxu.size();
        if(!n||!m)
            return v;
        stack<TreeNode*>s;
        TreeNode* root=new TreeNode(xianxu[0]);
        TreeNode* cur=root;
        for(int i=1,j=0;i<n;i++){
            if(cur->val!=zhongxu[j]){
                cur->left=new TreeNode(xianxu[i]);
                s.push(cur);
                cur=cur->left;
            }
            else {
                ++j;
                while(!s.empty()&&s.top()->val==zhongxu[j]){
                    cur=s.top();
                    s.pop();
                    ++j;
                }
                cur->right=new TreeNode(xianxu[i]);
                cur=cur->right;
            }
        }
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            int p=q.size();
            for(int i=0;i<p;i++){
                cur=q.front();
                q.pop();
                //            v.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
                if(i==p-1)
                    v.push_back(cur->val);
            }
        }
        return v;
    }
};