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

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...

MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...