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

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

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size())
        {
            struct TreeNode *root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
            root->val=pre.at(0);
            vector<int> pre1,pre2;
            vector<int> vin1,vin2;

            vector<int>::iterator iter=find(vin.begin(),vin.end(),root->val);
            int pst=iter-vin.begin();

            vin1.assign(vin.begin(),iter);
            vin2.assign(iter+1,vin.end());
            pre1.assign(pre.begin()+1,pre.begin()+pst+1);
            pre2.assign(pre.begin()+pst+1,pre.end());

            root->left=reConstructBinaryTree(pre1,vin1);
            root->right=reConstructBinaryTree(pre2,vin2);

            return root;
        }

        return NULL;
    }

    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        //重建二叉树
        struct TreeNode* root=reConstructBinaryTree(xianxu, zhongxu);

        //打印右视图
        struct TreeNode* end1=root,*end2=root;
        struct TreeNode* now=NULL;
        queue<struct TreeNode*> que;
        vector<int> ret;
        que.push(root);
        while(!que.empty())
        {
            now=que.front();
            que.pop();

            if(now->left!=NULL)
            {
                que.push(now->left);
                end2=now->left;
            }
            if(now->right!=NULL)
            {
                que.push(now->right);
                end2=now->right;
            }

            if(now==end1)
            {
                ret.push_back(now->val);
                end1=end2;
            }

        }
        return ret;

    }
};