力扣爆刷第141天之二叉树十连刷(翻转、对称、深度、平衡、路径)

news/2024/7/22 13:56:13/文章来源:https://blog.csdn.net/qq_43511039/article/details/139128744

力扣爆刷第141天之二叉树十连刷(翻转、对称、深度、平衡、路径)

文章目录

      • 力扣爆刷第141天之二叉树十连刷(翻转、对称、深度、平衡、路径)
      • 一、226. 翻转二叉树
      • 二、101. 对称二叉树
      • 三、104. 二叉树的最大深度
      • 四、111. 二叉树的最小深度
      • 五、222. 完全二叉树的节点个数
      • 六、110. 平衡二叉树
      • 七、257. 二叉树的所有路径
      • 八、404. 左叶子之和
      • 九、513. 找树左下角的值
      • 十、112. 路径总和

一、226. 翻转二叉树

题目链接:https://leetcode.cn/problems/invert-binary-tree/description/
思路:直接前序遍历,然后在遍历的过程中交换左右子节点。

class Solution {public TreeNode invertTree(TreeNode root) {traverse(root);return root;}void traverse(TreeNode root) {if(root == null) return ;TreeNode t = root.left;root.left = root.right;root.right = t;traverse(root.left);traverse(root.right);}}

二、101. 对称二叉树

题目链接:https://leetcode.cn/problems/symmetric-tree/description/
思路:将一个棵二叉树当做两颗二叉树来遍历,也就是在递归的函数参数中携带左右两颗子树,然后进行比较。

class Solution {public boolean isSymmetric(TreeNode root) {return traverse(root.left, root.right);}boolean traverse(TreeNode node1, TreeNode node2) {if(node1 == null && node2 == null) return true;if(node1 == null || node2 == null) return false;if(node1.val != node2.val) return false;return traverse(node1.left, node2.right) && traverse(node1.right, node2.left);}}

三、104. 二叉树的最大深度

题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
思路:后序遍历,返回左右子树的最大值即可,然后每返回一层就加1,即可得到最大深度。

class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}
}

四、111. 二叉树的最小深度

题目链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
思路:求最小深度,需要从上往下找,使用前序遍历,递归终点为叶子节点,到达叶子节点进行判断。

class Solution {int min = Integer.MAX_VALUE;public int minDepth(TreeNode root) {if(root == null) return 0;traverse(root, 1);return min;}void traverse(TreeNode root, int deep) {if(root == null) return;if(root.left == null && root.right == null) {min = Math.min(min, deep);return ;}traverse(root.left, deep+1);traverse(root.right, deep+1);}
}

五、222. 完全二叉树的节点个数

题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/description/
思路:求完全二叉树的节点个数,思路很简单,就是利用完全二叉树的性质,可以根据深度计算个数,所以就前序遍历,每一个节点都判断是否是完全二叉树,是就不遍历了,不是再遍历。

class Solution {public int countNodes(TreeNode root) {if(root == null) return 0;int a = 0, b = 0;TreeNode p = root, q = root;while(p != null) {a++;p = p.left;}while(q != null) {b++;q = q.right;}if(a == b) return (int)Math.pow(2, a) - 1;return countNodes(root.left) + countNodes(root.right) + 1;}
}

六、110. 平衡二叉树

题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/
思路:平衡二叉树是指左右子高度相差不超过1,所以直接按照求树的深度就可以解题,只要左右深度大于1,即不平衡。

class Solution {boolean flag = true;public boolean isBalanced(TreeNode root) {traverse(root);return flag;}int traverse(TreeNode root) {if(root == null) return 0;int left = traverse(root.left);int right = traverse(root.right);if(Math.abs(left - right) > 1) {flag = false;}return Math.max(left, right) + 1;}
}

七、257. 二叉树的所有路径

题目链接:https://leetcode.cn/problems/binary-tree-paths/description/
思路:求所有路径,这种题目在回溯中非常常见,所以本题也是在递归的过程中使用回溯,在叶子节点进行路径组装。

class Solution {List<String> result = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {traverse(root);return result;}void traverse(TreeNode root) {list.add(root.val);if(root.left == null && root.right == null) {StringBuilder sb = new StringBuilder();for(int i : list) {sb.append(i).append("->");}sb.delete(sb.length()-2, sb.length());result.add(sb.toString());return;}if(root.left != null) {traverse(root.left);list.remove(list.size()-1);}if(root.right != null) {traverse(root.right);list.remove(list.size()-1);}}
}

八、404. 左叶子之和

题目链接:https://leetcode.cn/problems/sum-of-left-leaves/description/
思路:求左叶子之和,求的是所有的左叶子的和,所以只需要做两件事情,一件是在叶子节点进行判断,另外一件是提供每个节点的信息,用于判断当前节点是否是叶子节点,这种信息需要从父节点传递,所以在递归函数的参数中。

class Solution {int sum = 0;public int sumOfLeftLeaves(TreeNode root) {traverse(root, false);return sum;}void traverse(TreeNode root, boolean flag) {if(root == null) return ;if(root.left == null && root.right == null && flag) {sum += root.val;}traverse(root.left, true);traverse(root.right, false);}
}

九、513. 找树左下角的值

题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/description/
思路:本题和上一题略有差异,上一题是求所有左叶子节点的和,要求的是左叶子节点,本题类似于树的左视图,但是是深度最深的哪一行的最左边的那个节点,它可能是左节点也可能是右节点。只需要前序遍历,利用深度,当深度第一次大于记录值时,说明是第一次到达下一层,而且采用的是前序遍历,到达的是下一层的最左边的叶子节点。

class Solution {int result = 0, max = 0;public int findBottomLeftValue(TreeNode root) {traverse(root, 1);return result;}void traverse(TreeNode root, int deep) {if(root == null) return ;if(root.left == null && root.right == null && deep > max) {max = deep;result = root.val;} traverse(root.left, deep + 1);traverse(root.right, deep + 1);}
}

十、112. 路径总和

题目链接:https://leetcode.cn/problems/path-sum/description/
思路:求路径总和,类似于回溯的用法,就是在树的递归过程中使用回溯,如果是全局变量,需要手动回滚数据,如果是携带是函数参数列表则不需要。

class Solution {boolean flag = false;public boolean hasPathSum(TreeNode root, int targetSum) {traverse(root, targetSum, 0);return flag;}void traverse(TreeNode root, int targetSum, int sum) {if(root == null || flag) return;sum += root.val;if(root.left == null && root.right == null) {if(sum == targetSum) flag = true;}traverse(root.left, targetSum, sum);traverse(root.right, targetSum, sum);}
}

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

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

相关文章

30.哀家要长脑子了!---栈与队列

1.388. 文件的最长绝对路径 - 力扣&#xff08;LeetCode&#xff09; 其实看懂了就还好 用一个栈来保存所遍历过最大的文件的绝对路径的长度&#xff0c;栈顶元素是文件的长度&#xff0c;栈中元素的个数是该文件目录的深度&#xff0c;非栈顶元素就是当时目录的长度 检查此…

Leetcode260

260. 只出现一次的数字 III - 力扣&#xff08;LeetCode&#xff09; class Solution {public int[] singleNumber(int[] nums) {//通过异或操作,使得最终结果为两个只出现一次的元素的异或值int filterResult 0;for(int num:nums){filterResult^num;}//计算首个1(从右侧开始)…

单元测试(了解)

单元测试定义 针对最小功能单元&#xff08;方法&#xff09;&#xff0c;编写测试代码对其进行正确性测试 之前如何进行单元测试&#xff1f;有什么问题&#xff1f; main中编写测试代码&#xff0c;调用方法测试 问题&#xff1a; 无法自动化测试 每个方法的测试可能不是…

如何在go项目中实现发送邮箱验证码、邮箱+验证码登录

前期准备 GoLand &#xff1a;2024.1.1 下载官网&#xff1a;https://www.jetbrains.com/zh-cn/go/download/other.html Postman&#xff1a; 下载官网&#xff1a;https://www.postman.com/downloads/ 效果图(使用Postman) Google&#xff1a; QQ&#xff1a; And …

部署LAMP平台

目录 一、LAMP简介与概述 1.1 各组件作用 1.2 LAMP平台搭建时各组件安装顺序 1.3 httpd服务的目录结构 1.4 httpd.conf配置文件 二、编译安装Apache httpd服务 2.1 关闭防火墙&#xff0c;将安装Apache所需软件包传到/opt目录下 2.2 安装环境依赖包 ​2.3 配置软件模块…

01Python相关基础学习

Python基础 模块相关导入模块sys模块 模块相关 导入模块 1. import 模块名 2. import 模块名 as 别名 3. from 模块名 import 成员名 as 别名sys模块 1. sys.argv 介绍: 实现从程序的外部想程序传递参数返回的是一个列表,第一个元素是程序文件名,第二个元素是程序外部传入的…

【前端三剑客之HTML】详解HTML

1. HTML(超文本标记语言) HTML意为超文本标记语言&#xff0c;其可以通过标签把其他网页/图片/视频等资源引入到当前网页中&#xff0c;让网页最终呈现出来的效果超越了文本.HTML是一种标记语言&#xff0c;其是由一系列标签组成的. 而且每个标签都有特定的含义和确定的页面显…

网络其他重要协议(DNS、ICMP、NAT)

1.DNS DNS是一整套从域名映射到IP的系统 1.1 DNS背景 TCP/IP中使用IP地址和端口号来确定网络上的一台主机的一个程序&#xff0c;但是IP地址不方便记忆&#xff0c;例如我们想访问百度就会在浏览器中输入baidu.com而不是百度的IP地址。于是人们发明了一种叫主机名的东西, 是…

BFS解决最短路问题(详解)

目录 BFS简介 && 框架&#xff1a; 一.二叉树的最小深度 二&#xff1a;迷宫中里入口最近的出口&#xff1a; 三.最小基因变化: 四&#xff1a;单词接龙&#xff1a; ​五&#xff1a;为高尔夫比赛砍树&#xff1a; BFS简介 && 框架&#xff1a; 说到BFS…

在C++中自定义命名空间,在命名空间中定义string变量,同时定义一个函数实现单词逆置

代码 #include <iostream> #include <cstring> using namespace std; namespace my_space {string s;void reverse(string s);//定义逆置函数 } using namespace my_space; void my_space::reverse(string s){int lens.size();int i0;int jlen-1;while(i<j){//…

CIM模型

CIM 是 Esri 制图信息模型。 它是一个地图内容规范,用于记录在保存、读取、引用或打开时如何永久保留描述不同项目组件的信息。 该规范以 JSON 表示,适用于 ArcGIS 应用程序和 API 中的地图、场景、布局、图层、符号和样式。 CIM 不仅限于制图设置。 要了解属性的组织方式以及…

如何停止 iPad 和 iPhone 之间共享短信,独立接收和发送消息

概括 在当今高度互联的数字世界中&#xff0c;Apple 设备之间的无缝连接性提供了极大的便利&#xff0c;尤其是在消息同步方面。iPhone 和 iPad 用户通常可以享受到设备间短信的自动同步功能&#xff0c;这意味着无论是在哪个设备上&#xff0c;用户都可以接收和回复消息。然而…

六.逼格拉满-Prometheus+Grafana微服务监控告警

前言 微服务架构是一个分布式系统&#xff0c;由多个独立的服务组成&#xff0c;每个服务可能运行在不同的容器、虚拟机或物理机上&#xff0c;那么在生产环境中我们需要随时监控服务的状态&#xff0c;以应对各种突发情况&#xff0c;比如&#xff1a;内存爆满&#xff0c;CP…

【Oracle篇】rman工具实用指南:常用命令详解与实践(第二篇,总共八篇)

&#x1f4ab;《博主介绍》&#xff1a;✨又是一天没白过&#xff0c;我是奈斯&#xff0c;DBA一名✨ &#x1f4ab;《擅长领域》&#xff1a;✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux&#xff0c;也在扩展大数据方向的知识面✌️…

[NISACTF 2022]easyssrf、[NISACTF 2022]level-up

[NISACTF 2022]easyssrf 使用dirsearch扫描后没发现什么路径 尝试访问127.0.0.1&#xff0c;成功了 访问127.0.0.1/flag.php提示有文件/fl4g 使用file://协议读取文件/fl4g&#xff0c;提示除此页面外还有一个ha1x1ux1u.php页面。 file:///fl4g 直接访问&#xff0c;发现GET…

google浏览器下载和相应驱动下载

1、chromedriver 115及115之后版本下载地址&#xff1a; https://googlechromelabs.github.io/chrome-for-testing/ 2、chromedriver 115之前版本下载地址&#xff08;已停止更新115及之后版本&#xff09;&#xff1a; http://chromedriver.storage.googleapis.com/index.html…

PVE 虚拟机环境下删除 local-lvm分区

1、删除逻辑卷 lvremote pve/data 2、扩展逻辑卷 lvextend -l 100%FREE -r pve/root 3、 修改存储目录内容 点击 Datacenter - Storage &#xff08;1&#xff09;删除local-lvm分区 &#xff08;2&#xff09;编辑local分区&#xff0c;在内容一项中勾选所有可选项。

python数据处理与分析入门-Pandas数据可视化例子

相关内容 Matplotlib可视化练习 Pandas 数据可视化总结 柱状图 reviews[points].value_counts().sort_index().plot.bar()散点图 reviews[reviews[price] < 100].sample(100).plot.scatter(xprice, ypoints)蜂窝图 reviews[reviews[price] < 100].plot.hexbin(xprice…

C++:vector基础讲解

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起学习《C&#xff1a;vector基础讲解》&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 &#xff01; 如果本篇文章对你有帮助&#xff0c;还请各位点点赞&#xff01;&#…

分类和品牌关联

文章目录 1.数据库表设计1.多表关联设计2.创建表 2.使用renren-generator生成CRUD1.基本配置检查1.generator.properties2.application.yml 2.生成代码1.进入localhost:81生成代码2.将main目录覆盖sunliving-commodity模块的main目录 3.代码检查1.注释掉CategoryBrandRelationC…