每日一刷——二叉树的构建——12.12

第一题:最大二叉树

题目描述:654. 最大二叉树 - 力扣(LeetCode)

我的想法:

我感觉这个题目最开始大家都能想到的暴力做法就是遍历找到数组中的最大值,然后再遍历一遍,把在它左边的依次找到最大值,但是emmm,感觉效率很低,时间上肯定过不了

然后其实我会觉得这个题目跟大根堆和小根堆有一点像,,,就是先建立一个树来,然后如果大就上去,如果小就下来,但是有一点,怎么保证顺序??因为这样先建立一棵树来,再上移,好像不能保证??我浅浅画个图

那这样,是让6之后的全部向上移动吗,移动到6的右边? 

题目分析:

嗯,看了一圈,好像没有人用小根堆,大根堆写哈,有用单调栈写的,有用DFS写,然后其实我那个初始想法版本也行,因为我的题解给我的就是这样写的,但是有一点不一样的是:它分割了数组+递归,我就是憨憨的非要把每一步写出来哈,,其实每一个节点做的事情一样,就一定一定抽象出来然后递归

就是相当于先找到数组中的最大值,然后左右两边分别交给左右儿子再去做分割

其实这样我们可以总结一个思想就是:

其实每一个节点,都是首先把自己构造出来,然后想办法构造自己的左右子树,就相当于每一个人都有当孩子和当父亲的一天,你要在孩子时期规定此时要做的事,要在父亲时期规定要做的事,然后每一个人的框架都是如此,只不过最后做出来的成果可能不一样

我的错误题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 只要不断地传递就可以了,天哪噜
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums ,int lo,int hi){
        if(lo>hi)
            return null;
        
        int max=nums[lo];
        int index=lo;
        //找到数组中地最大值,然后构建这个节点,再分配左右儿子的数组
        for(int i=lo+1;i<=hi;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }

        //一般,数组,====>传递下标,而不是非得要找到这个数是多少

        //创建这个节点
        TreeNode root =new TreeNode(max);
        root.left=build(nums,lo,index-1);
        root.left=build(nums,index+1,hi);

        return root;
    }
}

其实这个错误原因很好分析,一看,我去,右边的好像都没进去,所以直接检查代码,发现root.right写错了,写成了root.left

题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 只要不断地传递就可以了,天哪噜
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums ,int lo,int hi){
        if(lo>hi)
            return null;
        
        int max=nums[lo];
        int index=lo;
        //找到数组中地最大值,然后构建这个节点,再分配左右儿子的数组
        for(int i=lo+1;i<=hi;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }

        //一般,数组,====>传递下标,而不是非得要找到这个数是多少

        //创建这个节点
        TreeNode root =new TreeNode(max);
        root.left=build(nums,lo,index-1);
        root.right=build(nums,index+1,hi);

        return root;
    }
}

这个题目想清楚了之后,代码写起来和思维都不是很难的

第二题:从前序与中序遍历序列构造二叉树

题目描述:105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

我的想法:

soga,这个!用前序和中序构建树,这个题目老师原来讲过,挺经典的题的

而且无论是前序还是后序,都必须要知道中序序列,才有唯一的二叉树确定

应该思路是这样的:

先从preorder里边开始,最开始是3  然后在inorder里边找3,3就把inorder分成了两半,左边是左子树里边的,右边就是右子树里边的,然后一直一直这样下去,最后这棵树就建好了(这里的思路有点小问题,看到后面就知道了)

我的题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        //1.建立头节点
        //拿到头节点在inorder中的位置,然后分割左右
        //左边就是新的inorder 右边也是新的inorder
        //2.建立左右子节点

        //3.什么时候结束?
        int index=0;
        return build(index,preorder,inorder,0,inorder.length-1);
        
    }

    public static TreeNode build(int index,int[] preorder, int[] inorder,int lf,int lr){
        if(lf<lr)
            return null;

        int findplace=0; 
        TreeNode root =new TreeNode(preorder[index-1]);
        index++;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                findplace=i;
                break;
            }
        }
        //突然感觉index传的不对啊???  这个index是互通的吗??
        root.left=build(index,preorder,inorder,lf,findplace-1);
        root.right=build(index,preorder,inorder,findplace+1,lr);
        return root;
    }
}

为啥越界了???

题目分析:

for循环遍历确定index效率不高,可以考虑进一步优化:

因为题目说二叉树结点的值不重复,所以我们可以使用一个hashmap存储元素到索引的映射,这样就可以直接通过hashMap查到rootVal对应的index!!

我天!!!我知道了我的有一点的错误了!!

就是在preorder里边遍历,其实是不需要一个一个遍历,怎么说呢,因为你一直把index传给左右两颗子树,但是其实左右两颗子树里边需要的index并不相同,因为它们的元素就不相同,所以这样干,没有考虑周到,笑死我了,根据下面这张图应该能很明显的看到:preorder其实把它分成了这样两个部分

 也就是说现在想指向某个值在数组里边对应的下标的时候,可以不需要遍历,直接用hashmap映射就可以了,它的值就是它的下标

题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public static HashMap<Integer,Integer> valToIndex =new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        //1.建立头节点
        //拿到头节点在inorder中的位置,然后分割左右
        //左边就是新的inorder 右边也是新的inorder
        //2.建立左右子节点

        //3.什么时候结束?

        //HashMap优化
        
        for(int i=0;i<preorder.length;i++){
            valToIndex.put(inorder[i],i);
        }
        
        return build(0,preorder.length-1,preorder,inorder,0,inorder.length-1);
        
    }

    public static TreeNode build(int preFirst,int preLast,int[] preorder, int[] inorder,int lf,int lr){
        if(preFirst>preLast)
            return null;

        //分步完善  rootVal   index   leftSize
        int rootVal =preorder[preFirst];

        int index=valToIndex.get(rootVal);

        int leftSize=index-lf;

        //构造父结点
        TreeNode root =new TreeNode(rootVal);

        /*有了hashmap这一步可以简化了
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                findplace=i;
                break;
            }
        } 
        */
        root.left=build(preFirst+1 , preFirst+leftSize , preorder , inorder , lf , index-1);
        root.right=build(preFirst+leftSize+1 , preLast , preorder , inorder , index+1 , lr);
        return root;
    }
}

第三题:根据前序和后序遍历构造二叉树

题目描述:889. 根据前序和后序遍历构造二叉树 - 力扣(LeetCode)

我的想法:

我没有想法,惹惹惹,我在想这两个题有啥区别

我的题解:

题目分析:

前两道题:可以通过前序或者后序遍历找到根节点,然后根据中序遍历结果确定左右子树

但这一道题,可以确定根节点,但是无法确切的知道左右子树有哪些节点

比如:

但是解法还是和前两道题差别不大,通过控制左右子树的索引来构建

1.首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素作为根节点的值

2.然后把前序遍历结果的第二个元素作为左子树的根节点的值

3.在后序遍历结果中寻找左子树跟节点的值,从而确定了左子树的索引边界,进而确定右子树的索引边界,然后递归构造左右子树即可 

题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //依然是下标到数的hash映射
    HashMap<Integer,Integer> valToIndex =new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for(int i=0;i<postorder.length;i++){
            valToIndex.put(postorder[i],i);
        }

        return build(preorder,0,preorder.length-1,
                     postorder,0,postorder.length-1);

    }


    TreeNode build(int[] preorder,int preStart ,int preEnd,
                   int[] postorder,int postStart,int postEnd){

             if(preStart > preEnd)
                return null;

             if(preStart==preEnd)
                return new TreeNode(preorder[preStart]);

            //root节点对应的值就是前序遍历数组的第一个元素
            int rootVal =preorder[preStart];

            //root.left 的值是前序遍历元素第二个元素
            //通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
            //确定preorder  和postorder 中左右子树的元素区间
            int leftRootVal =preorder[preStart+1];  

            //leftRootVal 在后序遍历数组中的索引
            int index =valToIndex.get(leftRootVal);

            //左子树的元素个数
            int leftSize =index-postStart +1;

            //先构造出当前根节点
            TreeNode root =new TreeNode(rootVal);
            //递归构造左右子树
            //根据左子树的根节点索引和元素个数推导左右子树的索引边界
            root.left =build(preorder,preStart+1,preStart+leftSize,postorder,postStart,index);
            root.right =build(preorder,preStart+leftSize+1,preEnd,postorder,index+1,preEnd-1); //是因为左闭右开吗??         
            //好像因为要用到两个,preorder里边,一次性用两个,第一个为头节点,第二个为左孩子节点
    
            return root;
    }
}

我要背题目!!阿巴

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/935310.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯刷题——day2

蓝桥杯刷题——day2 题目一题干题目解析代码 题目二题干解题思路代码 题目一 题干 三步问题。有个小孩正在上楼梯&#xff0c;楼梯有n阶台阶&#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法&#xff0c;计算小孩有多少种上楼梯的方式。结果可能很大&#xff0c;你需要…

中粮凤凰里共有产权看房记

中粮凤凰里看房是希望而来&#xff0c;失望而归。主要是对如下失望&#xff0c;下述仅个人看房感受&#xff1a; 1. 户型不喜欢&#xff1a;三房的厨房和餐厅位置很奇葩 2. 样板间在25楼&#xff1a;湖景一言难尽和有工厂噪声 3. 精装修的交房质量:阳台的推拉门用料很草率 …

负载均衡和tomcat

一、负载均衡 1.相关概念 nginx的反向代理<-->负载均衡 负载均衡 将四层或者是七层的请求分配到多台后端的服务器上&#xff0c;从而分担整个业务的负载。提高系统的稳定性&#xff0c;也可以提供高可用&#xff08;备灾&#xff0c;其中的一台后端服务器如果发生故障…

电子电工一课一得

首语 在现代社会中&#xff0c;电子电工技术已经渗透到我们生活的方方面面&#xff0c;从家用电器到工业自动化&#xff0c;从通信设备到智能系统&#xff0c;无一不依赖于电子电工技术。因此&#xff0c;掌握电子电工的基础知识&#xff0c;不仅对理工科学生至关重要&#xf…

Pyside6 --Qt设计师--简单了解各个控件的作用之:Buttons

目录 一、BUttons1.1 包含1.2 不同按钮的解释 二、具体应用2.1 Push Button2.2 Tool Button2.3 Radio Button2.4 Check Box2.5 Command Link Button2.6 Dialog Button Box2.6.1 直接显示代码如下2.6.2 可以修改ok&#xff0c;cancel 的内容 今天学习一下工具箱里面的Buttons&am…

网络基础 - TCP/IP 五层模型

文章目录 一、OSI 参考模型中各个分层的作用1、应用层2、表示层3、会话层4、传输层5、网络层6、数据链路层7、物理层 一、OSI 参考模型中各个分层的作用 1、应用层 2、表示层 负责设备固有数据格式和网络标准数据格式间的转换 3、会话层 4、传输层 负责连接的建立和断开&…

【git】git回退到之前版本+拓展git命令

一、问题 git提交有时候会出错&#xff0c;想回退到之前的版本 1、命令git reset --soft <commit_id> commit_id【回退到的编号】 2、git push --force-with-lease origin <branch_name> branch_name【分支名】 二、拓展 1、git bash 1、进入任意磁盘 cd 磁盘…

Tomcat项目本地部署

不依赖idea部署本地项目&#xff0c;这里使用哈米音乐为例。 哈米音乐项目为聚合项目&#xff0c;ham-parent为父模块&#xff0c;其余为子模块。 ham-console:后台模块 ham-core:公共模块 ham-file:图片模块 ham-portal:前台模块 需要将这些模块进行打包&#xff0c;点击右侧…

【数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】

目录&#x1f60b; 任务描述 测试说明 我的通关代码: 测试结果&#xff1a; 任务描述 本关任务&#xff1a;实现二路归并算法。 测试说明 平台会对你编写的代码进行测试&#xff1a; 测试输入示例&#xff1a; 11 18 2 20 34 12 32 6 16 5 8 1 (说明&#xff1a;第一行是元…

东方明珠生成式人工智能媒体融合创新平台荣获AI Cloud轻量云典型案例

近日&#xff0c;由全球数字经济大会组委会主办&#xff0c;中国信息通信研究院&#xff08;以下简称“信通院”&#xff09;、中国通信企业协会承办的2024全球数字经济大会云AI计算国际合作论坛在北京成功召开。会上隆重发布了2024年“AI Cloud助力大模型场景化和工程化落地”…

高阶数据结构--B树B+树实现原理B树模拟实现--Java

目录 一、B-树概念 二、B-树插入分析 1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下&#xff1a; 2.插入过程总结 三、B树插入实现 四、B树 1.B树概念 2.B树的特性 五、B树应用 1.索引 2.Mysql索引 3.InnoDB 一、B-树概念 1970 年&#xff0c; R.Bayer 和…

优选算法——分治(快排)

1. 颜色分类 题目链接&#xff1a;75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; 题目展示&#xff1a; 题目分析&#xff1a;本题其实就要将数组最终分成3块儿&#xff0c;这也是后面快排的优化思路&#xff0c;具体大家来看下图。 这里我们上来先定义了3个指针&…

Edge SCDN的独特优势有哪些?

强大的边缘计算能力 Edge SCDN&#xff08;边缘安全加速&#xff09;是酷盾安全推出的边缘集分布式 DDoS 防护、CC 防护、WAF 防护、BOT 行为分析为一体的安全加速解决方案。通过边缘缓存技术&#xff0c;智能调度使用户就近获取所需内容&#xff0c;为用户提供稳定快速的访问…

「Mac玩转仓颉内测版45」小学奥数篇8 - 排列组合计算

本篇将通过 Python 和 Cangjie 双语讲解如何计算排列与组合。这道题目旨在让学生学会使用排列组合公式解决实际问题&#xff0c;并加深对数学知识和编程逻辑的理解。 关键词 小学奥数Python Cangjie排列与组合 一、题目描述 编写一个程序&#xff0c;计算从 n 个不同元素中取…

基于Q-Learning的机器人栅格地图路径规划,可以更改地图大小及起始点,可以自定义障碍物,MATLAB代码

基于Q-learning算法的栅格地图路径规划是一种利用强化学习技术来解决路径规划问题的方法。 状态空间定义&#xff1a;在路径规划任务中&#xff0c;状态通常代表机器人或智能体在环境中的位置。状态空间可以是离散的&#xff0c;如网格地图上的特定位置。 动作空间定义&#x…

中电金信携手中远海科,共启贸易金融数智新篇章

在数智化转型成为驱动经济社会高质量发展的新引擎背景下&#xff0c;“数智方案”栏目聚焦金融等国计民生重点行业场景&#xff0c;依托中电金信“源启筑基咨询引领应用重构”的产品及服务体系&#xff0c;输出市场洞察和行业解决方案、应用案例&#xff0c;旨在全面推动行业IT…

抗DDOS设备

0x00 定义: 抗DDOS设备顾名思义&#xff0c;就是防御DDoS攻击的设备&#xff0c;通常包含三个部分&#xff1a;检测中心、清洗中心和管理中心 检测中心主要负责对流量进行检测&#xff0c;发现流量异常后上报管理中心&#xff0c;由管理中心下发引流策略至清洗中心&#xff0…

游戏引擎学习第42天

仓库: https://gitee.com/mrxiao_com/2d_game 简介 目前我们正在研究的内容是如何构建一个基本的游戏引擎。我们将深入了解游戏开发的每一个环节&#xff0c;从最基础的技术实现到高级的游戏编程。 角色移动代码 我们主要讨论的是角色的移动代码。我一直希望能够使用一些基…

Node一、fs 模块、path 模块、端口号、 http 模块、

一、Node.js了解 Node.js是一个跨平台JavaScript运行环境&#xff0c;使开发者可以搭建服务器端的JavaScript应用程序。 概念&#xff1a;使用 Node.js 编写后端程序 / 支持前端工程化 ✓ 后端程序&#xff1a;提供接口和数据&#xff0c;网页资源等 ✓ 前端工程化 &#x…

游戏引擎学习第44天

仓库: https://gitee.com/mrxiao_com/2d_game 向量数学的重要性 矢量数学非常重要&#xff0c;因为 它在某种程度上类似于将C和C视为高于汇编语言的语言&#xff0c;从而使得我们能够以略高的层次思考问题&#xff0c;同时保留大部分性能好处和直接访问的类型。这种思维方式就…