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

输出二叉树的右视图

https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

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;

       
    }
};

全部评论

相关推荐

今天 13:43
门头沟学院 Java
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务