【java数据结构】二叉树OJ题
【java数据结构】二叉树OJ题
- 一、检查两颗树是否相同
- 二、另一颗树的子树
- 三、翻转二叉树
- 四、对称二叉树
- 五、判断一颗二叉树是否是平衡二叉树
- 六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
- 七、根据一棵树的前序遍历与中序遍历构造二叉树
- 练习:
- 八、二叉树前序非递归遍历实现
- 练习:
- 练习:
博客最后附有整篇博客的全部代码!!!
一、检查两颗树是否相同
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
检查两颗树是否相同
解题思路:
1.先判断两棵树是否都为空,都为空则两棵树是相等的;反之一棵树为空,另一棵树不为空,则两棵树不是相同二叉树。
2.分别进行遍历两棵树的左右节点,判断其节点的值是否相等。
public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q==null)return true;if(p==null||q==null)return false;if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
二、另一颗树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
另一颗树的子树
解题思路1:
1.先判断SubRoot是否为空,为空则一定是子树;下来判断Root是否为空,为空则返回false。
2.自己定义了一个方法isSame(TreeNode p,TreeNode q)来判断遍历的树的左右节点的值是否相同。
3. return isSubtree(root.left,subRoot)||
4. isSubtree(root.right,subRoot)||isSame(root,subRoot);这段代码的意思:先用isSubtree(TreeNode root, TreeNode subRoot)这个方法遍历Root树的左右节点,然后每当遍历到一个节点的时候,都将该节点作为Root节点的树和SubRoot树传入到isSame(TreeNode p,TreeNode q)这个方法中进行判断这两棵树是否相同,但凡相同则返回true;反之,如果遍历完每个节点都和SubRoot树没有完全相同的树,则SubRoot就不是Root树的子树。
public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRoot==null)return true;if(root==null)return false;return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSame(root,subRoot);}public boolean isSame(TreeNode p,TreeNode q){if(p==null&&q==null)return true;if(p==null||q==null||p.val!=q.val)return false;return isSame(p.left,q.left)&&isSame(p.right,q.right);}
三、翻转二叉树
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
翻转二叉树
解题思路:
1.先判断Root树是否为空,为空则返回null。
2.递归树的每一个节点的左右节点,并用定义的TreeNode类型的left和right来进行接收每一个节点的左右节点。
3.最后将left和right互换。
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;}
四、对称二叉树
给你一个二叉树的根节点 root , 检查它是否轴对称。
对称二叉树
解题思路:
和判断两棵树是否相同的思路相等,不同点是判断的是p的左节点和q的右节点、p的右节点和q的左节点是否相同。
public boolean isSymmetric(TreeNode root) {if(root==null)return true;TreeNode p=root.left;TreeNode q=root.right;return isSame(p,q);}public boolean isSame(TreeNode p,TreeNode q){if(p==null&&q==null)return true;if(p==null||q==null||p.val!=q.val)return false;return isSame(p.left,q.right)&&isSame(p.right,q.left);}
五、判断一颗二叉树是否是平衡二叉树
给定一个二叉树,判断它是否是 平衡二叉树。
判断一颗二叉树是否是平衡二叉树
解题思路1:
时间复杂度为:O(N^2)
1.先判断树是否为空。
2.遍历每一个节点,求每一个节点的左右高度,判断该节点的左右高度差是否大于1。
public boolean isBalanced(TreeNode root) {if(root==null)return true;int leftHight=getHeight(root.left);int rightHight=getHeight(root.right);return Math.abs(leftHight-rightHight)<=1 && isBalanced(root.left) && isBalanced(root.right);}int getHeight(TreeNode root) {if (root == null) return 0;int leftH = getHeight(root.left);int rightH = getHeight(root.right);return leftH > rightH ? leftH + 1 : rightH + 1;}
解题思路2:
时间复杂度:O(N)。
自下而上计算每个节点的高度,判断每个节点是否是平衡二叉树,如果是返回该节点的高度,反之返回-1。
public boolean isBalanced2(TreeNode root) {return getHeight2(root)>=0;}int getHeight2(TreeNode root) {if (root == null) return 0;int leftH = getHeight2(root.left);if(leftH<0){return -1;}int rightH = getHeight2(root.right);if(rightH>=0&&Math.abs(leftH - rightH) <= 1){return Math.max(leftH, rightH) + 1;}return -1;}
六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
解题思路1:
1.先判断树是否为空,为空则返回null。
2.开始遍历树的每一个节点,找到p或q的节点,然后返回。
3.如果都找到了则返回Root节点,这里的Root节点肯定不是p或q的本身;如果没找到q节点,则公共祖先就是q节点;反之。
(此思路,当找到一个节点时,就不会继续遍历该节点的子节点)。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null)return null;if(root==p||root==q)return root;TreeNode lefttree=lowestCommonAncestor(root.left,p,q);TreeNode righttree=lowestCommonAncestor(root.right,p,q);if(lefttree!=null&&righttree!=null){return root;}else if(lefttree!=null){return lefttree;}else{return righttree;}}
解题思路2:
1.定义两个栈s1,s2。用来保存root节点到目标节点p、q的节点数。
2.判断两个栈的长度,pop()出栈中元素个数多的栈,让两个栈中元素个数相同。
3.peek()两个栈栈顶元素,判断是否相同,相同则就是公共祖先;不同则pop()出两栈顶元素。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode> s1=new Stack<>();Stack<TreeNode> s2=new Stack<>();getPath(root,p,s1);getPath(root,q,s2);if(s1.size()>s2.size()){int len=s1.size()-s2.size();while(len!=0){s1.pop();len--;}}else{int len=s2.size()-s1.size();while(len!=0){s2.pop();len--;}}while(!s1.isEmpty()&&!s2.isEmpty()){if(s1.peek()==s2.peek()){return s1.peek();}else{s1.pop();s2.pop();}}return null;}public boolean getPath(TreeNode root,TreeNode target,Stack<TreeNode> stack){if(root==null) return false;stack.push(root);if(root==target) return true;if(getPath(root.left,target,stack)){return true;}if(getPath(root.right,target,stack)){return true;}stack.pop();return false;}
七、根据一棵树的前序遍历与中序遍历构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
根据一棵树的前序遍历与中序遍历构造二叉树
解题思路:
1.定义一个:buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend)方法,用来构建二叉树,int[] preorder:前序遍历。 int[] inorder:中序遍历。int inbegin:标记中序遍历数组的起始位置。int inend:标记中序遍历数组的末尾。
2.定义一个私有方法:findVal(int[] inorder,int inbegin,int inend,int val),用来在中序遍历中找到根节点的位置。此时返回的int值左边的值就是左子树,右边的值就是右子树。
public int preIndex=0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {//这种情况下 表明 当前root 没有子树了 if(inbegin > inend) {return null;}TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findVal(inorder,inbegin,inend,preorder[preIndex]);preIndex++;root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}private int findVal(int[] inorder,int inbegin,int inend,int val) {for(int i = inbegin ;i <= inend;i++) {if(inorder[i] == val) {return i;}}return -1;}
练习:
根据一棵树的中序遍历与后序遍历构造二叉树
八、二叉树前序非递归遍历实现
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
二叉树前序非递归遍历实现
解题思路:
1.先判断root树是否为空。
2.定义一个栈和node=root;node开始往左遍历,遍历一个将node.val放入链表中,然后将node放入栈中;当node==null时,node=stack.pop();遍历node右边的。
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();if(root==null)return list;Stack<TreeNode> stack=new Stack<>();TreeNode node=root;while(node!=null||!stack.isEmpty()) {while (node != null) {list.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return list;}
练习:
二叉树的中序遍历非递归
练习:
二叉树的后序遍历非递归
此篇博客的全部代码!!!
相关文章:

【java数据结构】二叉树OJ题
【java数据结构】二叉树OJ题 一、检查两颗树是否相同二、另一颗树的子树三、翻转二叉树四、对称二叉树五、判断一颗二叉树是否是平衡二叉树六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先七、根据一棵树的前序遍历与中序遍历构造二叉树练习:八、二叉树前…...

IIC和SPI的时序图
SCL的变化快慢决定了通信速率,当SCL为低电平的时候,无论SDA是1还是0都不识别: ACK应答:当从设备为低电平的时候识别为从设备有应答: 谁接收,谁应答: 起始位和停止位: IIC的时序图&am…...

MySQL数据库表的操作
1、总述 今天我跟大家分享MySQL数据库中表的创建,查看,修改,删除。 2、创建表 create table table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; 说明࿱…...
.net core 创建linux服务,并实现服务的自我更新
目录 创建服务创建另一个服务,用于执行更新操作给你的用户配置一些systemctl命令权限 创建服务 /etc/systemd/system下新建服务配置文件:yourapp.service,内容如下: [Unit] Descriptionyourapp Afternetwork.target[Service] Ty…...

springboot338it职业生涯规划系统--论文pf(论文+源码)_kaic
毕 业 设 计(论 文) 题目:it职业生涯规划系统的设计与实现 摘 要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以…...
oracle将select作为字段查询
在Oracle中,如果你想将一个SELECT语句作为字段的值,你可以使用子查询或者使用WITH子句(也称为公用表表达式CTE)。以下是两种方法的示例: 方法1:使用子查询 语法如下: SELECTcolumn1,(SELECT …...
Java数据结构和算法相关面试题
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...

网络安全风险评估
项目背景 随着信息化技术的快速发展,特别是面向社会、政府机构、企业等业务系统的投入使用,各组织机构对网络和信息系统安全防护都提出了新的要求。为满足安全需求,需对组织机构的网络和信息系统的安全进行一次系统全面的评估,以…...

ADAM优化算法与学习率调度器:深度学习中的关键工具
深度学习模型的训练效果离不开优化算法和学习率的选择。ADAM(Adaptive Moment Estimation)作为深度学习领域中广泛应用的优化算法之一,以其高效性和鲁棒性成为许多任务的默认选择。而学习率调度器则是优化算法的“助推器”,帮助训…...
岛屿数量C++11新特性
每日一题 200. 岛屿数量 class Solution {//使用深度的优先搜索来搜索岛屿图//遍历整个图片 当char数组的值为1时开始从这个点开始往外扩散搜索//注意处理边界 图不是正方形 public:int ans;int d[4][2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};int N;int M;void dfs(vector<…...

Git 快速入门:全面了解与安装步骤
Git 快速入门:全面了解与安装步骤 一、关于Git 1.1 简介 Git 是一个开源的分布式版本控制系统,由 Linus Torvalds 于 2005 年创建,最初是为了更好地管理 Linux 内核开发而设计。 Git用于跟踪计算机文件的变化,特别是源代码文件…...

基于域自适应的双光融合
目录 引言DAF-Net编码器-解码器分支编码器部分融合层解码器部分 域自适应层概述多核最大均值差异(MK-MMD)第一阶段:编码器-解码器分支训练训练过程损失函数 第二阶段:融合层训练训练过程损失函数 实验与结果总结 文章声明…...
迭代器模式 (Iterator Pattern)
文章目录 迭代器模式 (Iterator Pattern)原理优点缺点示例代码场景描述1. 定义迭代器接口2. 定义集合接口3. 实现具体集合类4. 客户端代码输出结果 UML 类图使用场景优化与扩展小结 迭代器模式 (Iterator Pattern) 迭代器模式是一种 行为型设计模式,用于顺序访问集…...

039集——渐变色之:CAD中画彩虹()(CAD—C#二次开发入门)
(来左边儿 跟我一起画个龙,在你右边儿 画一道彩虹 ~~~~~~~~~~~ ) 效果如下: namespace AcTools {public class Class1{public Wform.Timer timer;//定时器需建在类下面public static DateTime startTime;[CommandM…...

如何将 GitHub 私有仓库(private)转换为公共仓库(public)
文章目录 如何将 GitHub 私有仓库转换为公共仓库步骤 1: 登录 GitHub步骤 2: 导航到目标仓库步骤 3: 访问仓库设置步骤 4: 更改仓库可见性步骤 5: 确认更改步骤 6: 验证更改注意事项 如何将 GitHub 私有仓库转换为公共仓库 在软件开发领域,GitHub 是一个广受欢迎的…...

C++11 右值引用
目录 左值 右值 左值引用与右值引用比较 左值引用总结: 右值引用总结: 左值引用的使用场景: 引用传参和做返回值都可以提高效率(减少拷贝) 左值引用的短板: 右值引用和移动语义解决上述问题: 下面就是有移动…...
WPS表格学习计划与策略
一、学习目标 掌握WPS表格的基本操作:包括新建、打开、保存工作簿,单元格的编辑与格式化,数据的输入与验证等。熟练运用WPS表格的数据处理功能:包括数据排序、筛选、分类汇总,以及使用公式和函数进行计算和分析。学会制作图表与数据可视化:掌握不同类型图表(如柱状图、折…...
Android 引入 proto 项目及使用方法
Proto(Protocol Buffers)是Google开发的一种语言无关、平台无关的序列化结构数据的方法,它类似于JSON和XML,但相对于XML而言更小,相对于JSON而言解析更快,支持多语言。以下是将Proto引入Android项目的方法及…...
VSOMEIP主要流程的时序
请求服务: client应用: application_impl::request_service routing_manager_client::request_service (老版本是routing_manager_proxy) routing_manager_client::send_request_services protocol::request_service_command its_command; // 创建…...
右值引用和移动语义:
C 右值引用和移动语义详解 在 C 的发展历程中,右值引用和移动语义的引入带来了显著的性能提升和编程灵活性。本文将深入探讨右值引用和移动语义的概念、用法以及重要性。 一、引言 C 作为一门高效的编程语言,一直在不断演进以满足现代软件编程的需求。…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...