当前位置: 首页 > news >正文

【Java刷题】二叉树

  1. 相同的树
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;
}
  1. 另一棵树的子树
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);
}
  1. 翻转二叉树
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;
}
  1. 平衡二叉树
// 方式一
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;
}
  1. 对称二叉树
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);
}
  1. 二叉树遍历
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();}}
}
  1. 二叉树的层序遍历
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;
}
  1. 二叉树的最近公共祖先
// 方式一
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();
}
  1. 从前序与中序遍历序列构造二叉树
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);
}
  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);
}
  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();
}
  1. 二叉树的前序遍历
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;
}
  1. 二叉树的中序遍历
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;
}
  1. 二叉树的后序遍历
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;
}
  1. 判断一棵树是不是完全二叉树
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】程序地址空间之动态库的加载

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

LabVIEW处理大量数据时,怎样确保数据的准确性和完整性?

在LabVIEW处理中&#xff0c;确保大量数据的准确性和完整性至关重要。以下是详细的多角度分析和建议&#xff0c;以确保在LabVIEW中处理大量数据时&#xff0c;数据的准确性和完整性&#xff1a; 1. 数据采集阶段 1.1 高精度硬件选择 选择高精度的数据采集硬件&#xff0c;如…...

容器是什么?

概念 容器可以被看作是一种轻量级的虚拟化技术。与传统虚拟化技术相比&#xff0c;容器不需要为每个应用程序提供单独的操作系统&#xff0c;它们共享宿主机的操作系统内核。这使得容器更加轻便和高效。 想象一下&#xff0c;容器就像是一艘艘可以在海洋中独立航行的货轮&…...

#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 结合个人风格 结论 前言 在当今的数字时代&#xff0c;人工…...

git rebase

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

Docker引起的漏洞问题

前言 测试环境上的中间件和java应用都是由docker进行部署的,但是因为docker的镜像访问有时候需要外网,由此引发了问题,在docker文件中 /usr/lib/systemd/system/docker.service 原有的配置为,可以看到进行了加密 ExecStart/usr/bin/dockerd --tlsverify --tlscacert/etc/docker…...

Oracle基本数据类型

在Oracle数据库中&#xff0c;数据类型是描述数据存储格式的属性。不同的数据类型允许存储不同种类的数据。以下是Oracle中的一些基本数据类型&#xff1a; 1. 字符数据类型 - CHAR(size): 定长字符数据&#xff0c;最大长度为2000字节。 - VARCHAR2(size): 变长字符数据…...

VS+QT+OCC创建坐标界面

1、安装并配置好项目后&#xff0c;填写如下代码&#xff1a; #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是一个打包工具&#xff0c;可以把JS、CSS、Node Module、Coffeescrip、SCSS/LESS、图片等都打包在一起&#xff0c;因此&#xff0c;现在几乎所有的SPA项目、JS项目都会用到Webpack。 官网&#xff1a;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内网穿透&#xff0c;实现公网访问 3. 设置固定连接公网地址 前言 作者简介&#xff1a; 懒大王敲代码&#xff0…...

Cochrane Library循证医学数据库的介绍及文献下载

今天要讲的数据库是Cochrane Library循证医学数据库&#xff0c;我们先来了解一下该数据库&#xff1a; Cochrane Library是国际Cochrane Collaboration的主要产品&#xff0c;由英国Wiley InterScience公司出版发行。是一个提供高质量证据的数据库&#xff0c;是循证医学的证…...

冯喜运:6.12今日黄金原油行情还会涨吗?黄金原油独家操作策略

【黄金消息面分析】&#xff1a;据荷兰国际集团(ING)大宗商品策略师埃瓦?曼西(Ewa Manthey)称&#xff0c;黄金价格正面临来自美元走强和中国需求疲软的新阻力&#xff0c;但一旦美联储开始降息&#xff0c;黄金价格将恢复反弹。      【黄金技术面分析】&#xff1a;黄金…...

VM ubuntu终端使用Host代理的方法

1、设置网络地址转换NAT 2、在终端敲击如下命令 先敲击 ip route show 找到网关。再敲击如下命令&#xff1a; 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&#xff1a;一种新型的通用语言模型预训练方法 随着人工智能技术的不断进步&#xff0c;自然语言处理&#xff08;NLP&#xff09;领域也迎来了革命性的发展。OpenAI的ChatGPT及其后续产品在全球范围内引起了广泛关注&#xff0c;展示了大型语言模型&#xff08;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…...

一文介绍暗区突围手游 游戏特色、具体玩法和独特的玩法体验

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 《暗区突围》是一款由腾讯魔方工作室群开发的第一人称射击游戏&#xff0c;于 2022 年 7 月 13 日正式公测&#xff0c;支持 Android 和 iOS 平台。这款游戏以从虚构的暗区收集物资并安全撤离作为最终目…...

Unity基础(三)3D场景搭建

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

在Spring Boot中使用Sa-Token实现路径拦截和特定接口放行

在Spring Boot中使用Sa-Token实现路径拦截和特定接口放行 很喜欢的一段话&#xff1a;别想太多&#xff0c;好好生活&#xff0c;也许日子过着过着就会有答案&#xff0c;努力走着走着就会有温柔的着落。 春在路上&#xff0c;花在枝上&#xff0c;所有的美好都在路上&#xff…...

接口测试中缓存处理策略

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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

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

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

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

MFC 抛体运动模拟:常见问题解决与界面美化

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

mac 安装homebrew (nvm 及git)

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