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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    //我的思路为首先根据先序遍历和中序遍历恢复这颗二叉树建然后再层序遍历二叉树输出每一层的最后一个元素
    //想好思路后本题就很简单了
    struct TreeNode{//二叉树节点类型
        int data;
        TreeNode*left;
        TreeNode*right;
    };
    TreeNode*root=NULL;
    vector<int> res;
    //该函数的含义为根据先序和中序建立一颗二叉树并返回头结点
    TreeNode* crTree(vector<int> xianxu,vector<int> zhongxu){
        if(xianxu.size()<=0){//说明已经是空树了
            return NULL;
        }
        TreeNode*root=new TreeNode;
        root->data=xianxu[0];//先序遍历的第一个节点就是这个树的头结点
        //在中序数组中找到这个节点的位置
        int index=0;
        for(;index<zhongxu.size();index++){
            if(zhongxu[index]==xianxu[0])
                break;
        }
        //利用这个数在中序数组中的位置把先序数组和中序数组分割成左右子树两个数组
        vector<int> leftpre(xianxu.begin()+1,xianxu.begin()+1+index);
        vector<int> rightpre(xianxu.begin()+1+index,xianxu.end());
        vector<int> leftin(zhongxu.begin(),zhongxu.begin()+index);
        vector<int> rightin(zhongxu.begin()+index+1,zhongxu.end());
        root->left=crTree(leftpre, leftin);
        root->right=crTree(rightpre, rightin);
        return root;
    }
    //层序遍历二叉树记录每一层的最后一个值
    void level(TreeNode*rt){
        if(rt==NULL)
            return;
        queue<TreeNode*> que;
        que.push(rt);
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode*node=que.front();
                que.pop();
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
                if(i==size-1){//说明是本行的最后一个了
                    res.push_back(node->data);
                }
            }
        }
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        root=crTree( xianxu, zhongxu);
        level(root);
        return res;
    }
};