【Java刷题】二叉树
- 相同的树
public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null) {return true;} else if(p != null && q != null) {if(p.val != q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}}return false;
}
- 另一棵树的子树
public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null) {return true;} else if(p != null && q != null) {if(p.val != q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}}return false;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null) {return false;}return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
- 翻转二叉树
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;
}
- 平衡二叉树
// 方式一
public int getHeight(TreeNode root) {if(root == null) {return 0;}return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
public boolean isBalanced(TreeNode root) {if(root == null) {return true;}if( Math.abs(getHeight(root.left) - getHeight(root.right)) > 1 ) {return false;}return isBalanced(root.left) && isBalanced(root.right);
}// 方式二 - 优化
public int getHeight(TreeNode root) {if(root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if( leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1 ) {return -1;}return 1 + Math.max(leftHeight, rightHeight);
}
public boolean isBalanced(TreeNode root) {return getHeight(root) >= 0;
}
- 对称二叉树
public boolean isSymmetricHelper(TreeNode left, TreeNode right) {if(left == null && right == null) {return true;} else if(left != null && right != null) {if(left.val != right.val) {return false;} else {return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);}}return false;
}
public boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return isSymmetricHelper(root.left, root.right);
}
- 二叉树遍历
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}public class Main {public static int i;public static TreeNode createTree(String str) {TreeNode root = null;char c = str.charAt(i++);if(c != '#') {root = new TreeNode(c);root.left = createTree(str);root.right = createTree(str);}return root;}public static void inorder(TreeNode root) {if(root == null) {return;}inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {String str = in.nextLine();i = 0;TreeNode root = createTree(str);inorder(root);System.out.println();}}
}
- 二叉树的层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if(root == null) {return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> row = new ArrayList<>();while (size > 0) {TreeNode peek = queue.peek();if(peek.left != null) {queue.offer(peek.left);}if(peek.right != null) {queue.offer(peek.right);}row.add(queue.remove().val);--size;}ret.add(row);}return ret;
}
- 二叉树的最近公共祖先
// 方式一
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return root;if(root == p || root == q) {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) {return left;} else {return right;}
}// 方式二
public boolean lowestCommonAncestorHelper(TreeNode root, TreeNode tofind, Stack<TreeNode> stack) {if(root == null) return false;stack.push(root);if(root == tofind) return true;if(lowestCommonAncestorHelper(root.left, tofind, stack) || lowestCommonAncestorHelper(root.right, tofind, stack)) {return true;} else {stack.pop();return false;}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();lowestCommonAncestorHelper(root, p, stack1);lowestCommonAncestorHelper(root, q, stack2);while(stack1.size() > stack2.size()) {stack1.pop();}while(stack1.size() < stack2.size()) {stack2.pop();}while(stack1.peek() != stack2.peek()) {stack1.pop();stack2.pop();}return stack1.peek();
}
- 从前序与中序遍历序列构造二叉树
public int step = 0;
public TreeNode buildTreeHelper(int[] preorder, int[] inorder, int start, int end) {if(start > end) return null;TreeNode root = new TreeNode(preorder[step++]);int i = 0;for ( ; i <= end; i++) {if (inorder[i] == root.val) {break;}}root.left = buildTreeHelper(preorder, inorder, start, i - 1);root.right = buildTreeHelper(preorder, inorder, i + 1, end);return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeHelper(preorder, inorder, 0, inorder.length - 1);
}
- 从中序与后序遍历序列构造二叉树
public int step;
public TreeNode buildTreeHelper(int[] postorder, int[] inorder, int start, int end) {if(start > end) return null;TreeNode root = new TreeNode(postorder[step--]);int i = 0;for ( ; i <= end; i++) {if (inorder[i] == root.val) {break;}}// 构建顺序相对前序 交换一下root.right = buildTreeHelper(postorder, inorder, i + 1, end);root.left = buildTreeHelper(postorder, inorder, start, i - 1);return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {step = postorder.length - 1;return buildTreeHelper(postorder, inorder, 0, inorder.length - 1);
}
- 根据二叉树创建字符串
public String tree2str(TreeNode root) {if(root == null) return "";StringBuilder str = new StringBuilder();str.append(root.val);if(root.left != null || root.right != null) {str.append('(');str.append(tree2str(root.left));str.append(')');}if(root.right != null) {str.append('(');str.append(tree2str(root.right));str.append(')');}return str.toString();
}
- 二叉树的前序遍历
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) return list;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);list.add(cur.val);cur = cur.left;}top = stack.pop();cur = top.right;}return list;
}
- 二叉树的中序遍历
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) return list;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);cur = cur.left;}top = stack.pop();list.add(top.val);cur = top.right;}return list;
}
- 二叉树的后序遍历
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) return list;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);cur = cur.left;}top = stack.peek();cur = top.right;if(cur == null) {TreeNode tmp = stack.pop();list.add(tmp.val);while(!stack.isEmpty() && stack.peek().right == tmp) {tmp = stack.pop();list.add(tmp.val);}}}return list;
}
- 判断一棵树是不是完全二叉树
boolean isCompleteTree(TreeNode root) {if(root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (true) {TreeNode top = queue.poll();if(top != null) {queue.offer(top.left);queue.offer(top.right);} else {break;}}while (!queue.isEmpty()) {if(queue.poll() != null) {return false;}}return true;
}
相关文章:
【Java刷题】二叉树
相同的树 public boolean isSameTree(TreeNode p, TreeNode q) {if(p null && q null) {return true;} else if(p ! null && q ! null) {if(p.val ! q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.rig…...

【Linux】程序地址空间之动态库的加载
我们先进行一个整体轮廓的了解,随后在深入理解细节。 在动态库加载之前还要说一下程序的加载,因为理解了程序的加载对动态库会有更深的理解。 轮廓: 首先,不管是程序还是动态库刚开始都是在磁盘中的,想要执行对应的可…...

LabVIEW处理大量数据时,怎样确保数据的准确性和完整性?
在LabVIEW处理中,确保大量数据的准确性和完整性至关重要。以下是详细的多角度分析和建议,以确保在LabVIEW中处理大量数据时,数据的准确性和完整性: 1. 数据采集阶段 1.1 高精度硬件选择 选择高精度的数据采集硬件,如…...
容器是什么?
概念 容器可以被看作是一种轻量级的虚拟化技术。与传统虚拟化技术相比,容器不需要为每个应用程序提供单独的操作系统,它们共享宿主机的操作系统内核。这使得容器更加轻便和高效。 想象一下,容器就像是一艘艘可以在海洋中独立航行的货轮&…...
#15 从Stable Diffusion生成的艺术中寻找灵感
文章目录 前言1. Stable Diffusion简介2. 寻找灵感的途径2.1 深入探索主题2.2 结合多种艺术风格2.3 实验不同的创意组合 3. 灵感应用3.1 艺术创作3.2 设计项目3.3 故事讲述 4. 实践建议4.1 记录和迭代4.2 开放实验4.3 结合个人风格 结论 前言 在当今的数字时代,人工…...

git rebase
1. git rebase的意义 首先理解这个rebase,它的意思是re base,翻译过来就是“重新基于”。 意义是:重新整理当前分支的开发线,使其变成基于某个开发节点的开发线。 2. rebase用于并行开发 构造两个分支master和feature…...

Docker引起的漏洞问题
前言 测试环境上的中间件和java应用都是由docker进行部署的,但是因为docker的镜像访问有时候需要外网,由此引发了问题,在docker文件中 /usr/lib/systemd/system/docker.service 原有的配置为,可以看到进行了加密 ExecStart/usr/bin/dockerd --tlsverify --tlscacert/etc/docker…...
Oracle基本数据类型
在Oracle数据库中,数据类型是描述数据存储格式的属性。不同的数据类型允许存储不同种类的数据。以下是Oracle中的一些基本数据类型: 1. 字符数据类型 - CHAR(size): 定长字符数据,最大长度为2000字节。 - VARCHAR2(size): 变长字符数据…...

VS+QT+OCC创建坐标界面
1、安装并配置好项目后,填写如下代码: #pragma once#include <Standard_Handle.hxx> #include <V3d_Viewer.hxx> #include <OpenGl_GraphicDriver.hxx> #include <WNT_Window.hxx> #include <V3d_View.hxx> #include <…...

VUE2.7项目配置webpack打包-详细操作步骤
一、Webpack简介 Webpack是一个打包工具,可以把JS、CSS、Node Module、Coffeescrip、SCSS/LESS、图片等都打包在一起,因此,现在几乎所有的SPA项目、JS项目都会用到Webpack。 官网:https://webpack.js.org GitHub为https://git…...

Linux系统Docker部署Apache Superset并实现远程访问详细流程
目录 前言 1. 使用Docker部署Apache Superset 1.1 第一步安装docker 、docker compose 1.2 克隆superset代码到本地并使用docker compose启动 2. 安装cpolar内网穿透,实现公网访问 3. 设置固定连接公网地址 前言 作者简介: 懒大王敲代码࿰…...

Cochrane Library循证医学数据库的介绍及文献下载
今天要讲的数据库是Cochrane Library循证医学数据库,我们先来了解一下该数据库: Cochrane Library是国际Cochrane Collaboration的主要产品,由英国Wiley InterScience公司出版发行。是一个提供高质量证据的数据库,是循证医学的证…...

冯喜运:6.12今日黄金原油行情还会涨吗?黄金原油独家操作策略
【黄金消息面分析】:据荷兰国际集团(ING)大宗商品策略师埃瓦?曼西(Ewa Manthey)称,黄金价格正面临来自美元走强和中国需求疲软的新阻力,但一旦美联储开始降息,黄金价格将恢复反弹。 【黄金技术面分析】:黄金…...

VM ubuntu终端使用Host代理的方法
1、设置网络地址转换NAT 2、在终端敲击如下命令 先敲击 ip route show 找到网关。再敲击如下命令: export http_proxyhttp://10.0.2.2:33210 export https_proxyhttp://10.0.2.2:33210 export HTTP_PROXYhttp://10.0.2.2:33210/ export HTTPS_PROXYhttp://10.0.2.…...
【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 破译犯罪时间(100分) - 三语言AC题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📎在线评测链接 破译犯罪时间(100分) 🌍 评测功能需要订阅专栏后私信联系清…...

大模型学习之GLM结构
探索GLM:一种新型的通用语言模型预训练方法 随着人工智能技术的不断进步,自然语言处理(NLP)领域也迎来了革命性的发展。OpenAI的ChatGPT及其后续产品在全球范围内引起了广泛关注,展示了大型语言模型(LLM&a…...
C#类库打包支持多个版本的类库
修改csproj <Project Sdk"Microsoft.NET.Sdk"><PropertyGroup><TargetFrameworks>netcoreapp3.1;net5.0;net6.0;net7.0;net8.0</TargetFrameworks><PackageId>xxxx</PackageId><Version>1.0.0</Version><Author…...

一文介绍暗区突围手游 游戏特色、具体玩法和独特的玩法体验
🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 《暗区突围》是一款由腾讯魔方工作室群开发的第一人称射击游戏,于 2022 年 7 月 13 日正式公测,支持 Android 和 iOS 平台。这款游戏以从虚构的暗区收集物资并安全撤离作为最终目…...

Unity基础(三)3D场景搭建
目录 简介: 一.下载新手资源 二.创建基本地形 三.添加场景细节 四,添加水 五,其他 六. 总结 简介: 在 Unity 中进行 3D 场景搭建是创建富有立体感和真实感的虚拟环境的关键步骤。 首先,需要导入各种 3D 模型资源,如建筑物、角色、道具等。这些模…...

在Spring Boot中使用Sa-Token实现路径拦截和特定接口放行
在Spring Boot中使用Sa-Token实现路径拦截和特定接口放行 很喜欢的一段话:别想太多,好好生活,也许日子过着过着就会有答案,努力走着走着就会有温柔的着落。 春在路上,花在枝上,所有的美好都在路上ÿ…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...

C++中vector类型的介绍和使用
文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...