Leetcode二叉树部分笔记

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

Leetcode二叉树部分笔记

  • 1.二叉树的最大深度
  • 2.同样的树
  • 3.翻转二叉树
  • 4.对称二叉树
  • **5. **填充每个节点的下一个右侧节点指针 II**
  • 6. 二叉树展开为链表
  • 7. 路经总和
  • 8.完全二叉树的节点个数


1.二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
在这里插入图片描述
**解题思路:**如果用广度优先遍历的话,设置一个队列,quque.offer代表让节点进入队列,判断当前队列内还有没有值,如果有则把它的左右孩子放进来,并把size–,每清空一次队列,代表遍历了一层,建一个计数器每遍历一层,计数器加一。最终得到深度。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;}
}

**解题思路2:**使用深度优先遍历,采用递归:假设深度优先到最后一层,执行这个函数,左孩子为null,右孩子为null,左孩子执行这个函数,返回0,右孩子执行这个函数,也返回0。该节点返回1,它的上一层 leftHeight就成1了。同理,如果他的上一层没有右孩子,则右孩子返回0,则这个上一层返回2。以此类推。

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

2.同样的树

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

在这里插入图片描述
**解题思路:**使用深度优先遍历。假设p和q都到了最后一层,p,left == null,q.left ==null,因此函数返回true,同理p.right == null 并且q.right == null,同样返回true,这样该节点返回一个true,返回给上一层,看看第一层是不是都是true。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null && q==null){return true;}else if(p==null || q==null){return false;}else if(p.val != q.val){return false;}else{return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
}

3.翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
在这里插入图片描述
解题思路:假设在最后一层的两个节点,这两个节点的四个孩子都是null,返回他们本身就可以,这两个节点的上一层的父节点,接收到下面返回上来的left和right,并对这两个进行置换,把它自身返回上去,以此类推。

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

4.对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。
在这里插入图片描述
**解题思路:**也就是判断L.left和R.right 以及 L.right = R.left,是否都能同时到达最底部,如果没有则说明不对称。

class Solution {public boolean isSymmetric(TreeNode root) {return root == null || recur(root.left, root.right);}boolean recur(TreeNode L, TreeNode R) {if (L == null && R == null) return true;if (L == null || R == null || L.val != R.val) return false;return recur(L.left, R.right) && recur(L.right, R.left);}
}作者:Krahets
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

**5. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。

在这里插入图片描述

**解题思路:**层序遍历,设置一个指针,如果当前层的大小不为1,则说明后面还有,让这个指针的next指向poll出来的节点,再让指针更新,如果大小为1,则不做任何操作。

class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();Node last = null;for (int i = 1; i <= n; ++i) {Node f = queue.poll();if (f.left != null) {queue.offer(f.left);}if (f.right != null) {queue.offer(f.right);}if (i != 1) {last.next = f;}last = f;}}return root;}
}

6. 二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
在这里插入图片描述

**解题思路:**设置一个pre,专门寻找root节点的left孩子的最右侧孩子,到达最右侧后让最右侧的右指针指向root的右孩子,让root的右指针指向root的左孩子,再让root向下走,遍历一遍。

class Solution {public void flatten(TreeNode root) {while (root != null) { //左子树为 null,直接考虑下一个节点if (root.left == null) {root = root.right;} else {// 找左子树最右边的节点TreeNode pre = root.left;while (pre.right != null) {pre = pre.right;} //将原来的右子树接到左子树的最右边节点pre.right = root.right;// 将左子树插入到右子树的地方root.right = root.left;root.left = null;// 考虑下一个节点root = root.right;}}
}

7. 路经总和

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

叶子节点 是指没有子节点的节点。
在这里插入图片描述
**解题思路:**假设在最后一层,发现root.left == null && root.right ==null 则返回当前value和sum值是否相等的判断,如果相等,则说明成立,直接返回true,如果不相等则返回false。

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

8.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。

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

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

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

相关文章

如何用状态图进行设计06

独立的控制线程 扩展状态图也提供了获取无序的输入事件的方法。这意味着一个状态开始时&#xff0c;它可能位于一个或多个控制线程的交叉点。控制行为的每个独立线程都类似一个状态机&#xff0c;独自运行&#xff0c;互不干扰。因此&#xff0c;这些控制线程可能会同时发生状…

【多模态】MiniCPM-V多模态大模型使用学习

MiniCPM-V模型使用 前言1. 模型文件下载和选择2. 环境安装配置3. 模型微调3.1 qlora微调minicpm-v-int43.2 lora微调minicpm-v3.3 merge_lora3.4 lora微调后量化int4 4. 模型推理4.1 huggingface API4.2 swift API(A) swift&#xff08;不支持batch inference&#xff09;(B) s…

快速上手Neo4j图关系数据库

参考视频&#xff1a; 【IT老齐589】快速上手Neo4j网状关系图库 1 Neo4j简介 Neo4j是一个图数据库&#xff0c;是知识图谱的基础 在Neo4j中&#xff0c;数据的基本构建块包括&#xff1a; 节点(Nodes)关系(Relationships)属性(Properties)标签(Labels) 1.1 节点(Nodes) 节点…

Transformer: Attention Is All You Need (2017) 翻译

论文&#xff1a;Attention Is All You Need 下载地址如下: download: Transformer Attention Is All you need Attention Is All You Need 中文 《Attention Is All You Need》是《Transformer》模型的开创性论文&#xff0c;提出了一种全新的基于注意力机制的架构&#xf…

可视化报表如何制作?一文详解如何用报表工具开发可视化报表

在如今这个数据驱动的商业时代&#xff0c;众多企业正如火如荼地推进数字化转型&#xff0c;力求在激烈的市场竞争中占据先机。然而&#xff0c;随着业务规模的扩大和运营复杂度的提升&#xff0c;企业的数据量爆炸式增长&#xff0c;传统报表格式单一、信息呈现密集且不易解读…

Angular由一个bug说起之十二:网页页面持续占用CPU过高

随着网络日益发达&#xff0c;网页的内容也更加丰富&#xff0c;形式也更加多样化。而随之而来的性能问题也不容小觑。这篇文章我会根据我在实践中遇到的一个问题来总结&#xff0c;我在面对性能问题的一些解决步骤&#xff0c;希望能对大家有所启发。 查找问题原因 我接触的…

MATLAB图卷积神经网络GCN处理分子数据集节点分类研究

全文链接&#xff1a;https://tecdat.cn/?p38570 本文主要探讨了如何利用图卷积网络&#xff08;GCN&#xff09;对图中的节点进行分类。介绍了相关的数据处理、模型构建、训练及测试等环节&#xff0c;通过对分子数据集的操作实践&#xff0c;展示了完整的节点分类流程&#…

uniapp中vuex(全局共享)的应用

一、Vuex概述 1.1 官方解释 Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。 它采用集中式存储管理 应用的所有组件的状态&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化 - Vuex 也集成到 Vue 的官方调试工具 devtools extension&#xff0c;提供了诸…

华为云服务器搭建基于LNMP部署wordpress

Ubuntu系统搭建过程目录 一、检查环境1.1 检查是否安装Nginx1.2 检查是否安装Mysql1.3 检查是否安装PHP二、更新软件包以及安装所需要的依赖 三、安装Nginx3.1 下载并解压nginx3.2. 编译安装3.3 启动和停止和测试3.4 创建服务脚本3.5 Nginx目录 四、安装Mysql4.1 安全安装配置4…

ElasticSearch01-概述

零、文章目录 ElasticSearch01-概述 1、Elastic Stack &#xff08;1&#xff09;简介 官网地址&#xff1a;https://www.elastic.co/cn/ELK是一个免费开源的日志分析架构技术栈总称&#xff0c;包含三大基础组件&#xff0c;分别是Elasticsearch、Logstash、Kibana。但实际…

Python学习(二)—— 基础语法(上)

目录 一&#xff0c;表达式和常量和变量 1.1 表达式 1.2 变量 1.3 动态类型特性 1.4 输入 二&#xff0c;运算符 2.1 算术运算符 2.2 关系运算符 2.3 逻辑运算符 2.4 赋值运算符 2.5 练习 三&#xff0c;语句 3.1 条件语句 3.2 while循环 3.3 for循环 四&#…

Idea汉化插件Datagrip汉化插件

汉化插件 ‍ ‍ Chinese (Simplified) Language Pack / 中文语言包 ‍ 插件地址 ‍ 安装完了之后,如果还不是中文的怎么办 ‍ 需要手动设置 Seetings -> Appearance & Behavior -> System Settings -> Language and Region -> Language 修改为 [ Chi…

ansible 自动化运维工具(三)playbook剧本

目录 Playbook的定义 Playbook组成 Playbook命令 Playbook剧本编写格式 基本组件 Handlers处理器 tags标签 Facts组件 Register&#xff1a;注册变量 Debug模块 Playbook循环 With_items循环 With_dict循环&#xff08;字典循环&#xff09; With_nested循环&…

12.2【JAVA EXP4]next.js的各种问题,DEBUG,前端补强,前后端交互,springSecurity ,java 配置,h2数据库

在服务器组件中使用了 useState 这样的 React Hook。useState 只能在客户端组件中使用&#xff0c;而不能在服务器组件中使用。Next.js 的新架构&#xff08;App Router&#xff09;中&#xff0c;默认情况下&#xff0c;页面和布局组件是服务器组件&#xff0c;因此不能直接使…

Cursor重置机器码-解决Too many free trials.

参考文章&#xff1a;如何绕过Cursor的机器绑定限制 前言 在前面这篇文章无限使用Cursor指南中&#xff0c;我提到使用 无限邮箱 或者 删除账号并重新注册 的方法&#xff0c;来无限使用Cursor免费版。但是当在本机登录过3个账号后&#xff0c;就会报这个“Too many free tria…

【PlantUML系列】部署图(七)

一、部署图的组成部分 节点&#xff08;Node&#xff09;&#xff1a;使用node关键字定义一个节点&#xff0c;节点可以是服务器、数据库或其他硬件设备。组件&#xff08;Component&#xff09;&#xff1a;使用component关键字定义一个组件&#xff0c;组件可以是软件模块或服…

qt QCommandLineParser详解

1、概述 QCommandLineParser是Qt框架中提供的一个类&#xff0c;专门用于解析命令行参数。它简化了命令行参数的处理过程&#xff0c;使得开发者能够轻松定义、解析和验证命令行选项和参数。QCommandLineParser适用于需要从命令行获取输入的控制台应用程序&#xff0c;以及需要…

青少年夏令营管理系统的设计与开发(社团管理)(springboot+vue)+文档

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…

vue3-tp8-Element:对话框实现

效果 参考框架 Dialog 对话框 | Element Plus 具体实现 一、建立view页面 /src/views/TestView.vue 二、将路径写入路由 /src/router/index.js import { createRouter, createWebHistory } from vue-router import HomeView from ../views/HomeView.vueconst router create…

【鸿睿创智开发板试用】移植OpenCV 4到OpenHarmony 4.1

目录 目录 引言 编译系统镜像 (1) 下载代码后解压SDK (2) 下载docker镜像   (3) 编译OH 编译OpenCV 下载OpenCV源代码 构建编译配置文件 执行编译命令 安装库和头文件 测试 结语 引言 最近有个需求是在基于RK3568的OpenHarmony 4.1系统中使用OpenCV&#xff0c…