【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实现路径拦截和特定接口放行 很喜欢的一段话:别想太多,好好生活,也许日子过着过着就会有答案,努力走着走着就会有温柔的着落。 春在路上,花在枝上,所有的美好都在路上ÿ…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...