算法日记 14—16 day 二叉树

前两天没有更新,这次把之前的补上,大篇章。

直接冲!!!

题目:找树坐下角的值

513. 找树左下角的值 - 力扣(LeetCode)

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1
题目分析:

        方法一:层序遍历。层序是对树的每一层都去遍历,那么每一层的开始其实就是左下角的值。

        方法二:递归遍历。这里的左下角在递归法中应该是深度最大的的叶子节点,而不是树中最左边的节点。所以根据这个深度我们就能找到这个节点。

//方法一:层序遍历
public class Solution {public int FindBottomLeftValue(TreeNode root) {Queue<TreeNode> temp=new Queue<TreeNode>();if(root!=null){temp.Enqueue(root);}int res=root.val;while(temp.Count>0){int size=temp.Count;for(int i=0;i<size;i++){TreeNode t=temp.Dequeue();if(i==0){res=t.val;}if(t.left!=null){temp.Enqueue(t.left);}if(t.right!=null){temp.Enqueue(t.right);}}}return res;}
}//方法二:递归法
public class Solution {int maxDepth=-1;int res=0;public int FindBottomLeftValue(TreeNode root) {BackTracking(root,0);return res;}public void BackTracking(TreeNode root,int depth){if(root.left==null&&root.right==null){if(depth>maxDepth){maxDepth=depth;res=root.val;}}if(root.left!=null){BackTracking(root.left,depth+1);}if(root.right!=null){BackTracking(root.right,depth+1);}return;}
}

题目:路径总和

112. 路径总和 - 力扣(LeetCode)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点

 题目分析:

        寻找合适的路径,对树进行遍历,每次记录路径即可,加入回溯就能够遍历完所有路径了。题目要求返回一个布尔值,在遍历路径的时候将是否满足也返回出来判断是否提前结束遍历。

public class Solution {public bool HasPathSum(TreeNode root, int targetSum) {if(root==null) return false;return BackTracking(root,targetSum-root.val);}public bool BackTracking(TreeNode root,int target){if(root.left==null&&root.right==null&&target==0) return true; //满足条件if(root.left==null&&root.right==null&&target!=0) return false;if(root.left!=null){target-=root.left.val;if(BackTracking(root.left,target)) return true;//提前返回target+=root.left.val;}if(root.right!=null){target-=root.right.val;if(BackTracking(root.right,target)) return true;//提前返回target+=root.right.val;}return false;}
}

题目:从中序和后序遍历中构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode) 

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

题目分析: 

        中序遍历是左中右,后序遍历是左右中。就可以发现后序遍历数组中的最后一个值就是根节点,那么通过这个节点就可以在中序遍历中将根节点的左右子树分出来,然后继续通过后序遍历数组将左右子树继续划分。

看看代码:

public class Solution {public TreeNode BuildTree(int[] inorder, int[] postorder) {if(postorder.Length==0) return null;int m=postorder[postorder.Length-1];TreeNode root=new TreeNode(m);//根节点if(postorder.Length==1) return root;int index;for(index=0;index<inorder.Length;index++){//获取根节点在中序数组中的位置if(inorder[index]==m) break;}int[] in_Left=inorder.Take(index).ToArray();//划分数组int[] po_left=postorder.Take(index).ToArray();int[] in_right=inorder.Skip(index+1).ToArray();int[] po_right=postorder.Skip(index).Take(inorder.Length - index - 1).ToArray();root.left=BuildTree(in_Left,po_left);//递归继续划分root.right=BuildTree(in_right,po_right);return root;}
}

对于数组的划分,其实有好几种方式。比如代码中的Take()截取到哪里结束。Skip(),从哪里开始截取。还有..的方式。 

        除了通过中序以及后序来构建外,还有通过前序和中序构造二叉树。本质上和这一题是一样的。需要注意对数组的区间划分位置。

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

public class Solution {public TreeNode BuildTree(int[] preorder, int[] inorder) {if(preorder.Length==0) return null;int m=preorder[0];TreeNode root=new TreeNode(m);if(preorder.Length==1) return root;int index;for(index=0;index<inorder.Length;index++){if(inorder[index]==m) break;}int[] p_left=preorder.Skip(1).Take(index).ToArray();int[] p_right=preorder.Skip(index+1).ToArray();int[] i_left=inorder.Take(index).ToArray();int[] i_right=inorder.Skip(index+1).ToArray();root.left=BuildTree(p_left,i_left);root.right=BuildTree(p_right,i_right);return root;}
}

题目:最大二叉树

 654. 最大二叉树 - 力扣(LeetCode)

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 

示例 1:

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。- 空数组,无子节点。- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。- 空数组,无子节点。- 只有一个元素,所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。- 只有一个元素,所以子节点是一个值为 0 的节点。- 空数组,无子节点。
 题目分析:

        其实这一题和上一题很像,无非是只有一个数组。根据题目的意思每次选取数组中的最大值作为根节点,然后划分数组,左子数组是左子树,右边就是右子树。然后同样的方式继续划分数组。

public class Solution {public TreeNode ConstructMaximumBinaryTree(int[] nums) {if(nums.Length==0) return null;int index=Max(nums);//选取最大值索引TreeNode root=new TreeNode(nums[index]);if(nums.Length==1) return root;//数组长度为一,叶子节点int[] left=nums.Take(index).ToArray();//划分int[] right=nums.Skip(index+1).ToArray();root.left=ConstructMaximumBinaryTree(left);//递归root.right=ConstructMaximumBinaryTree(right);return root;}public int Max(int[] nums){int res=0;for(int i=0;i<nums.Length;i++){if(nums[res]<nums[i]) res=i;}return res;}
}

题目:合并二叉树

617. 合并二叉树 - 力扣(LeetCode) 

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

 题目分析:

        合并两个二叉树,那么将A的节点加载B上就好了。每次递归的时候将两个树的结点同时传入其中。

public class Solution {public TreeNode MergeTrees(TreeNode root1, TreeNode root2) {if(root1==null) return root2;if(root2==null) return root1;root1.val+=root2.val;root1.left=MergeTrees(root1.left,root2.left);root1.right=MergeTrees(root1.right,root2.right);return root1;}
}

题目:二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣(LeetCode)

给定二叉搜索树(BST)的根节点 root 和一个整数值 val

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

 题目分析:

        二叉搜索树还记得吗?二叉搜索树的结点值满足左<中<右。根据这个特性,每次递归之前判断当前的结点值和目标值的大小,在去选择递归左边还是右边。

public class Solution {public TreeNode SearchBST(TreeNode root, int val) {if (root == null || root.val == val) return root;if (root.val > val) return SearchBST(root.left, val);if (root.val < val) return SearchBST(root.right, val);return null;}
}

题目:验证二叉搜索树

98. 验证二叉搜索树 - 力扣(LeetCode) 

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
 题目分析:

        二叉搜索树的大小是左<中<右,这个顺序像什么呢?没错,树的中序遍历。这意味着二叉搜索树的中序遍历是一个递增的数组。所有验证搜索树就是验证中序数组的递增就好了。

public class Solution {long val=Int64.MinValue;public bool IsValidBST(TreeNode root) {if(root==null) return true;bool left=IsValidBST(root.left);if(root.val>val) val=root.val;else return false;bool right=IsValidBST(root.right);return left&&right;}
}

题目:二叉搜索树的最小绝对差值

530. 二叉搜索树的最小绝对差 - 力扣(LeetCode) 

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

 题目分析:

        同样是二叉搜索树,那我们就需要考虑利用中序遍历的特殊性了。题目求得是最小差值,因为中序遍历是递增的,那么这个最小差值一定是相邻的两个位置。

public class Solution {List<int> arr=new List<int>();public int GetMinimumDifference(TreeNode root) {if(root==null) return 0;GetArray(root);if(arr.Count<2) return 0;int res=arr[arr.Count-1];for(int i=1;i<arr.Count;i++){res=Math.Min(res,arr[i]-arr[i-1]);}return res;}//对于二叉搜索树而言,中序遍历是一个有序数组public void GetArray(TreeNode root){//获取中序遍历if(root==null) return;GetArray(root.left);arr.Add(root.val);GetArray(root.right);}
}

题目:二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣(LeetCode) 

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树
 题目分析:

        又是一个二叉搜索树。求众数,就是出现最多的元素。考虑遍历的特性,因为数组是递增的,那么这个众数的出现一定是连续的。所以遍历之后统计出现的次数再排序是不是就找出来众数。不过这种写法比较麻烦。

        那我们能不能再遍历的时候就把出现次数的统计以及众数的选择一起做了呢?

        当然没问题,起初的中序遍历,中结点的处理只是收集结点而已,那么再处理结点的时候我们去比较这个结点和上一个结点的值是否相等,如果相等,计数加一,如果不等,计数和当前众数的大小比较,确实是否替换众数。

public class Solution {List<int> arr=new List<int>();int prev;//前一个结点的值int maxNum;//众数int num;//出现频率public int[] FindMode(TreeNode root) {prev=int.MinValue;maxNum=0;num=0;GetArray(root);return arr.ToArray();}public void GetArray(TreeNode root){if(root==null) return;GetArray(root.left);//处理结点if(root.val==prev){num++;}else{prev=root.val;//重新统计num=1;}if(num==maxNum){arr.Add(root.val);}else if(num>maxNum){//更新众数maxNum=num;arr.Clear();arr.Add(root.val);}GetArray(root.right);}

题目:二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣(LeetCode) 

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
 题目分析:

        寻找公共祖先,那我们自底向上查找不就好了吗?那怎么自底向上查找呢,当然是回溯啦,将查找结果返回给上一层。如果两个结果都不为空,那么上层就是他们的最近公共祖先了,不过需要注意的是,一个结点也可以是他自己的祖先。

public class Solution {public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==p||root==q||root==null) return root;//找到结点或者遍历到了叶子节点TreeNode left=LowestCommonAncestor(root.left,p,q);//遍历左子树得到节点TreeNode right=LowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null) return root;else if(left==null&&right!=null) return right;else if(left!=null&&right==null) return left;else{return null;}}
}

 

对于更详细的解析与其他语言的代码块,可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目:52

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

第三十一章 Vue之路由(VueRouter)

目录 一、引言 1.1. 路由介绍 二、VueRouter 三、VueRouter的使用 3.1. 使用步骤&#xff08;52&#xff09; 3.2. 完整代码 3.2.1. main.js 3.2.2. App.vue 3.2.3. Friend.vue 3.2.4. My.vue 3.2.5. Find.vue 一、引言 1.1. 路由介绍 Vue中路由就是路径和组件的映…

特朗普钦定的编程语言!

大家好&#xff0c;我是程序员面试刷题平台的鸭鸭&#xff01; 鸭鸭昨天一直关注美国大选&#xff0c;最终川普获胜&#xff01;然后就刷到了一个图&#xff1a; 看到上面这张图片了吗&#xff1f; 你没有看错&#xff0c;特朗普也开始关心起 Java 了&#xff01;Java 的迷弟…

day20:三剑客——awk基础

一&#xff0c;概述 AWK 是一种用于处理文本和数据的编程语言&#xff0c;特别擅长用于处理格式化文本文件。它通过将输入数据分成字段&#xff0c;逐行进行处理&#xff0c;广泛应用于数据分析、文本处理和系统管理中。 二&#xff0c;使用方式 命令模式&#xff08;重点&a…

如何优化 B2B 转化率?这些步骤你不可不知

企业怎么才能把上网逛的人变成潜在买家&#xff0c;再进一步变成真金白银的付费客户呢&#xff1f;这对营销团队来说&#xff0c;可是头等大事。特别是在B2B这行&#xff0c;提升转化率&#xff08;CRO&#xff09;不光是任务&#xff0c;更是让营销更高效、收入噌噌涨的秘密武…

CPU Study-Multi-Port Cache

参考来源&#xff1a;《超标量处理器设计》—— 姚永斌 关于Multi-Port Cache可以参考&#xff1a;https://compas.cs.stonybrook.edu/~nhonarmand/courses/sp16/cse502/slides/04-caches.pdf 为了实现每个周期执行多条load/store指令&#xff0c;Cache必须支持多端口。 True…

Linux-c TCP服务模型

1、TCP模型&#xff0c;服务端与客户端的搭建时序图 2、TCP模型&#xff0c;在创建阶段和通信阶段&#xff0c;对套接字的理解 2.1、tcp连接阶段 2.2、tcp通信状态 一个服务端与多个客户端的通信状态 TCP与UDP的对比 &#xff08;下图是笔者理解所画&#xff0c;可能也许有错…

一文了解Android的Doze模式

Android 的 Doze 模式是一项省电功能&#xff0c;主要用于减少设备的功耗&#xff0c;特别是在屏幕关闭且设备长时间未被使用的情况下。Doze 模式在 Android 6.0&#xff08;API Level 23&#xff09;首次引入&#xff0c;并在后续版本中不断改进&#xff0c;以便更智能地管理后…

Redis设计与实现 学习笔记 第十六章 Sentinel

Sentinel&#xff08;哨岗、哨兵&#xff09;是Redis的高可用性&#xff08;high availability&#xff09;解决方案&#xff1a;由一个或多个Sentinel实例&#xff08;instance&#xff09;组成的Sentinel系统可以监视任意多个主服务器&#xff0c;以及这些主服务器属下的从服…

I.MX6U 裸机开发3. GPIO操作控制LED灯

I.MX6U 裸机开发3. GPIO操作控制LED灯 一、创建项目目录及源文件1. 新建目录2. 远程开发环境3. 创建源文件 二、代码编写1. 打开时钟2. 配置端口复用功能为GPIO3. 配置端口电气属性4. 设置GPIO方向&#xff08;GDIR寄存器&#xff09;5. 输出6. 死循环等待 三、编译程序1. 整体…

雷军-2022.8小米创业思考-11-新零售:用电商思维做新零售,极致的效率+极致的体验。也有弯路,重回极致效率的轨道上。

第十一章 新零售 当我们说到小米模式的时候&#xff0c;其实我们说的是两件东西&#xff1a; 一是小米模式的本质&#xff0c;即高效率的商业模式&#xff1b; 另一件是小米这家公司具象的商业模式&#xff0c;这是小米在实践中摸索、建立的一整套业务模型。 从2015年到202…

Java:多态的调用

1.什么是多态 允许不同类的对象对同一消息做不同的响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。&#xff08;发送消息就是函数调用&#xff09;。多态使用了一种动态绑定&#xff08;dynamic binding&#xff09;技术&#xff0c;指在执行期间判断所引用…

基于Python的学生宿舍管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

基于springboot+vue实现的网上预约挂号管理系统 (源码+L文+ppt)4-104

结合现有六和医院网上预约挂号管理系统的特点&#xff0c;应用新技术&#xff0c;构建了六和医院网上预约挂号管理系统。首先从需求出发&#xff0c;对目前传统的六和医院网上预约挂号管理进行了详细的了解和分析。根据需求分析结果&#xff0c;对系统进行了设计&#xff0c;并…

C++初阶(九)--初识模板

目录 引入 一、什么是模板 二、函数模板 1.函数模板的概念 2.函数模板的格式 template关键字 模板参数列表 3.函数模板的原理 4.函数模板的实例化 5.数模板的匹配原则 三、类模板 1.类模板的定义格式 2.类模板的实例化 引入 在编程的世界里&#xff0c;我们经常…

C语言 | Leetcode C语言题解之第537题复数乘法

题目&#xff1a; 题解&#xff1a; bool parseComplexNumber(const char * num, int * real, int * image) {char *token strtok(num, "");*real atoi(token);token strtok(NULL, "i");*image atoi(token);return true; };char * complexNumberMulti…

牛客网项目总结

下面这幅图是牛客网项目的架构图&#xff0c;最下层是Spring Boot&#xff0c;表示我们所有的技术都是基于Spring Boot&#xff0c;上面一层是Spring&#xff0c;Spring上面是Spring MVC、Spring MyBatis 和 Spring Security。 通过Spring MVC 解决前后端请求交互的问题&#…

想画一个沙漠掘金游戏地图

想画一个沙漠掘金游戏地图 沙漠掘金生成一个地图htmljs 沙漠掘金 沙漠掘金是一个企业培训课程游戏&#xff0c;规则大致是&#xff1a; 玩家从大本营出发&#xff0c;到达矿山掘金后返回&#xff0c;如果规定的天数未回来&#xff0c;则失败&#xff0c;如果回来&#xff0c;…

【Java爬虫的淘宝寻宝记】—— 淘宝商品类目的“藏宝图”

引言&#xff1a; 在淘宝这个广袤的“商品宇宙”中&#xff0c;每一件商品都是一颗璀璨的星球&#xff0c;而商品类目就是连接这些星球的星际航道。今天&#xff0c;我们将派遣一位勇敢的Java爬虫宇航员&#xff0c;去揭开这些星际航道背后的秘密——商品类目。准备好了吗&…

内网穿透-SSF内网穿透反向socks代理之渗透内网thinkphp主机上线msf

1 ssf 简介 Secure Socket Funneling socks正反向代理&#xff0c;linux版较好的免杀 1.1下载地址 https://github.com/securesocketfunneling/ssf 1.2下载编译好的执行文件 https://github.com/securesocketfunneling/ssf/releases/tag/3.0.0 2.环境 kali 攻击机 网卡 桥…

【HarmonyOS】键盘遮挡输入框UI布局处理

【HarmonyOS】键盘遮挡输入框UI布局处理 问题背景&#xff1a; 在开发输入框UI时&#xff0c;特别是登录页面的密码输入框靠下&#xff0c;或者是评论底部的pop弹框。 当我们输入框获得焦点后&#xff0c;键盘自下而上显示&#xff0c;一般情况下会遮挡住我们的UI布局。 导致…