题解 | #输出二叉树的右视图#复习一下重建二叉树

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


     void buildOrder(vector<int>& primeVec,map<int,int>& result){
        for(int i=0;i<primeVec.size();++i){
            result[primeVec[i]]=i;
        }
     }
    TreeNode* buildTree(int root,int left,int right,map<int,int>& preOrderMap,map<int,int>& inOrderMap,vector<int>& preOrder, vector<int>& inOrder){
        //cout<<"建造"<<root<<' '<<left<<' '<<right<<endl;
        //cout<<"左子树大小"<<inOrderMap[root]- inOrderMap[left]<<endl;
        TreeNode *curRoot=new TreeNode(root);

        if(root!=left)curRoot->left=buildTree(
            preOrder[preOrderMap[root]+1],
            left,
            inOrder[inOrderMap[root]-1],
            preOrderMap,inOrderMap,preOrder,inOrder
        );
        
        if(root!=right)curRoot->right=buildTree(
            preOrder[preOrderMap[root]+1+(inOrderMap[root]- inOrderMap[left])],
            inOrder[inOrderMap[root]+1],
            right,
            preOrderMap,inOrderMap,preOrder,inOrder
        );
        return curRoot;

     }

    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        //右视图的含义是只输出每一层最右元素，如果给了完整的二叉树可以用层次遍历
        //但是这道给的是前序遍历和中序遍历
        //如果重建二叉树当然是可以做的，但我觉得一道medium题目不该用这么heavy的解法，也想不到更好的，总之先写了，就当复习
        
        vector<int> result;
        if(!preOrder.size())return result;
        //创建索引
        map<int,int> preOrderMap,inOrderMap;
        buildOrder(preOrder, preOrderMap);
        buildOrder(inOrder, inOrderMap);
        //构建二叉树
        TreeNode *resultTree=buildTree(preOrder[0], inOrder[0],inOrder[inOrder.size()-1], preOrderMap, inOrderMap, preOrder, inOrder);
        //层次遍历
        deque<TreeNode*> temp={resultTree};
        int layerSize=1;
        TreeNode* cur;
        while(temp.size()){
            cur=temp.back();
            temp.pop_back();
            if(cur->left)temp.push_front(cur->left);
            if(cur->right)temp.push_front(cur->right);
            --layerSize;
            if(!layerSize){
                layerSize=temp.size();
                result.push_back(cur->val);
            }

        }


        return  result;

       
    }
};