leetcode——二叉树问题汇总
leetcode 144. 二叉树的前序遍历

①递归法:
/*** 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;ans.add(cur.val);traversal(cur.left,ans);traversal(cur.right,ans);}public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}
②迭代法:
/*** 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 List<Integer> preorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> ans = new ArrayList<>();if(root == null) return ans;stack.push(root);while(stack.size() != 0){TreeNode node = stack.pop();ans.add(node.val);if(node.right != null) stack.push(node.right);if(node.left != null) stack.push(node.left);}return ans;}
}
LinkedList可以用于模拟栈和队列, push和pop可以用于模拟栈,add()和remove()可以用于模拟队列。
leetcode 94. 二叉树的中序遍历

①递归法:
/*** 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;traversal(cur.left,ans);ans.add(cur.val);traversal(cur.right,ans);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}
②迭代法:
/*** 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 List<Integer> inorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> ans = new ArrayList<>();TreeNode cur = root;while(cur != null || stack.size() != 0){if(cur != null){stack.push(cur);cur = cur.left;//左}else{cur = stack.pop();ans.add(cur.val);//中cur = cur.right;//右}}return ans;}
}
leetcode 145. 二叉树的后序遍历
①递归法:
/*** 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 void traversal(TreeNode cur, List<Integer> ans){if(cur == null) return;traversal(cur.left,ans);traversal(cur.right,ans);ans.add(cur.val);}public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root,ans);return ans;}
}
leetcode 102. 二叉树的层序遍历
队列迭代法:
/*** 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 List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if(root != null) queue.add(root);while(queue.size() != 0){int size = queue.size();List<Integer> list = new ArrayList<>();for(int i=0; i<size; i++){TreeNode node = queue.remove();list.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}ans.add(list);}return ans;}
}
leetcode 226. 翻转二叉树

在层序遍历的代码上添加交换左右节点的逻辑即可:
/*** 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 invertTree(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();if(root != null) queue.add(root);while(queue.size() != 0){int size = queue.size();for(int i=0; i<size; i++){TreeNode node = queue.pop();//交换左右孩子节点TreeNode temp = node.left;node.left = node.right;node.right = temp;if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return root;}
}
leetcode 101. 对称二叉树

/*** 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 boolean isSymmetric(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root.left);queue.add(root.right);while(queue.size() != 0){TreeNode leftNode = queue.remove();TreeNode rightNode = queue.remove();if(leftNode == null && rightNode == null) continue;if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;queue.add(leftNode.left);queue.add(rightNode.right);queue.add(leftNode.right);queue.add(rightNode.left);}return true;}
}
leetcode 104. 二叉树的最大深度

本题在层序遍历的代码上修改即可,每一层代表深度+1:
/*** 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 int maxDepth(TreeNode root) {if(root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();int ans = 0;queue.add(root);while(queue.size() != 0){int size = queue.size();ans++;for(int i=0; i<size; i++){TreeNode node = queue.remove();if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}
leetcode 111. 二叉树的最小深度

大致思路和求二叉树最大深度类似,在内层while循环中加一句判断:当当前节点的左右节点都为空时,直接返回当前深度,此时也就是二叉树的最小深度。
/*** 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 int minDepth(TreeNode root) {if(root == null) return 0;int ans = 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size() != 0){int size = queue.size();ans++;for(int i=0; i<size; i++){TreeNode node = queue.remove();if(node.left == null && node.right == null) return ans;if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}
leetcode 222. 完全二叉树的节点个数

用层序遍历的逻辑做即可:
/*** 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 int countNodes(TreeNode root) {int ans = 0;if(root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size() != 0){int size = queue.size();for(int i=0; i<size; i++){ans++;TreeNode node = queue.remove();if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}return ans;}
}
leetcode 96. 不同的二叉搜索树

本题利用动态规划来做,分析当n=3的情况:
- 当1作为根节点,此时左子树有0个节点,右子树有2两个节点,此时的二叉树种数应该有dp[0]*dp[2]种。
- 当2作为根节点,此时左右子树各有一个节点,种数都是dp[1],此时的二叉树种数应该有dp[1]*dp[1]种。
- 当3作为根节点,此时情况和第一种情况类似,只是左右子树交换了。
class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i=2; i<=n; i++){for(int j=0; j<i; j++){dp[i] += dp[j] * dp[i-j-1];}}return dp[n];}
}
相关文章:
leetcode——二叉树问题汇总
leetcode 144. 二叉树的前序遍历 ①递归法: /*** 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,…...
Android基础开发-饿汉式申请权限
1、案例,打开app时,就要申请权限 直接在onCreateView中申请所有权限就可,然后在选择的回调里边判断申请的结果 package com.example.client;import android.Manifest; import android.content.Intent; import android.content.pm.PackageMa…...
java Day7 正则表达式|异常
文章目录 1、正则表达式1.1 常用1.2 字符串匹配,提取,分割 2、异常2.1 运行时异常2.2 编译时异常2.3 自定义异常2.3.1 自定义编译时异常2.3.2 自定义运行时异常 1、正则表达式 就是由一些特定的字符组成,完成一个特定的规则 可以用来校验数据…...
Python算法题集_搜索二维矩阵
Python算法题集_搜索二维矩阵 题74:搜索二维矩阵1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵展开为列表二分法】2) 改进版一【行*列区间二分法】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之…...
学习笔记:顺序表和链表(一、顺序表)
首先来个导言: 1.数组的优势:下标的随机访问,物理空间连续。数组指针用[ ]或者 * , 结构体指针用 - > 2.书写习惯 test.c写出主体框架 QelList.c写出结构体、头文件、函数声明 QelList.c写出函数的实现 3.挪动:如果从前…...
Midjourney从入门到实战:图像生成命令及参数详解
目录 0 专栏介绍1 Midjourney Bot常用命令2 Midjourney绘图指令格式3 Midjourney绘图指令参数3.1 模型及版本3.2 画面比例3.3 风格化3.4 图片质量3.5 混乱值3.6 随机数种子3.7 重复贴图3.8 停止3.8 垫图权重3.9 提示词权重分割 0 专栏介绍 🔥Midjourney是目前主流的…...
C语言分析基础排序算法——插入排序
目录 插入排序 直接插入排序 希尔排序 希尔排序基本思路解析 希尔排序优化思路解析 完整希尔排序文件 插入排序 直接插入排序 所谓直接插入排序,即每插入一个数据和之前的数据进行大小比较,如果较大放置在后面,较小放置在前面&#x…...
海格里斯HEGERLS智能托盘四向车系统为物流仓储自动化升级提供新答案
随着实体企业面临需求多样化、订单履行实时化、商业模式加速迭代等挑战,客户对物流仓储解决方案的需求也逐渐趋向于柔性化、智能化。作为近十年来发展起来的新型智能仓储设备,四向车系统正是弥补了先前托盘搬运领域柔性解决方案的空白。随着小车本体设计…...
SQLiteC/C++接口详细介绍-sqlite3类(一)
上一篇:SQLiteC/C接口简介 下一篇:SQLiteC/C接口详细介绍(二) 引言: SQLite C/C 数据库接口是一个流行的SQLite库使用形式,它允许开发者在C和C代码中嵌入 SQLite 基本功能的解决方案。通过 SQLite C/C 数据…...
基于UDP实现直播间聊天的功能
需求:软件划分为用户客户端和主播服务端两个软件client.c和server.c 用户客户端负责:1.接收用户的昵称2.接收用户输入的信息,能够将信息发送给服务端3.接收服务端回复的数据信息,并完成显示主播服务端负责:1.对所有加入直播间的用…...
html5cssjs代码 006 文章排版《桃花源记》
html5&css&js代码 006 文章排版《桃花源记》 一、代码二、解释页面整体结构:头部信息:CSS样式:文章内容: 这段代码定义了一个网页,用于展示文章《桃花源记》的内容。网页使用了CSS样式来定义各个部分的显示效果…...
勾八头歌之数据科学导论—数据采集实战
一、数据科学导论——数据采集基本概念 第1关:巧妇难为无米之炊 第2关:数据采集概念与内涵 二、数据科学导论——数据采集实战 第1关:单网页爬取 import urllib.request import csv import re# ********** Begin ********** # dataurllib.r…...
微信小程序云开发教程——墨刀原型工具入门(素材面板)
引言 作为一个小白,小北要怎么在短时间内快速学会微信小程序原型设计? “时间紧,任务重”,这意味着学习时必须把握微信小程序原型设计中的重点、难点,而非面面俱到。 要在短时间内理解、掌握一个工具的使用…...
C#与WPF通用类库
个人集成封装,仓库已公开 NetHelper 集成了一些常用的方法; 如通用的缓存静态操作类、常用的Wpf的ValueConverters、内置的委托类型、通用的反射加载dll操作类、Wpf的ViewModel、Command、Navigation、Messenger、部分常用UserControls(可绑定的Passwo…...
http协议中的强缓存与协商缓存,带图详解
此篇抽自本人之前的文章:http面试题整理 。 别急着跳转,先把缓存知识学会了~ http中的缓存分为两种:强缓存、协商缓存。 强缓存 响应头中的 status 是 200,相关字段有expires(http1.0),cache-control&…...
蓝桥杯2019年第十届省赛真题-修改数组
查重类题目,想到用标记数组记录是否出现过 但是最坏情况下可能会从头找到小尾巴,时间复杂度O(n2),数据范围106显然超时 再细看下题目,我们重复进行了寻找是否出现过,干脆把每个元素出现过的次数k记录下来,直…...
【Python使用】python高级进阶知识md总结第3篇:静态Web服务器-返回指定页面数据,静态Web服务器-多任务版【附代码文档】
python高级进阶全知识知识笔记总结完整教程(附代码资料)主要内容讲述:操作系统,虚拟机软件,Ubuntu操作系统,Linux内核及发行版,查看目录命令,切换目录命令,绝对路径和相对…...
ELK 日志分析系统
ELK (Elasticsearch、Logstash、Kibana)日志分析系统的好处是可以集中查看所有服务器日志,减轻了工作量,从安全性的角度来看,这种集中日志管理可以有效查询以及跟踪服务器被攻击的行为。 Elasticsearch 是个开源分布式…...
机器学习模型—逻辑回归
机器学习模型—逻辑回归 逻辑回归是一种用于分类任务的监督机器学习算法,其目标是预测实例属于给定类别的概率。逻辑回归是一种分析两个数据因素之间关系的统计算法。本文探讨了逻辑回归的基础知识、类型和实现。 什么是逻辑回归 逻辑回归用于二元分类,其中我们使用sigmoi…...
Ubuntu20.04 创建新的用户
1、了解Linux目录结构 推荐看一下:https://www.runoob.com/linux/linux-system-contents.html Linux支持多个用户进行操作的,这样提高了系统的安全性,也可以多人共用一个系统,不过要注意的是系统中安装的软件相关路径࿰…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
