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

二叉树相关算法

1、二叉树基本操作

二叉树的定义就不在这里多说了,下面这个图就是一个简单的二叉树:

二叉树的三种遍历方式:

前序遍历:头左右,也就是先头后左再右:1245367

    public static void prePrint(BinaryTreeNode root) {if (root != null) {System.err.print(root.val);prePrint(root.left);prePrint(root.right);}}

中序遍历:左头右,也就是先左后头再右:4251637

    public static void midPrint(BinaryTreeNode root) {if (root != null) {midPrint(root.left);System.err.print(root.val);midPrint(root.right);}}

后序遍历:左头右,也就是先左后右再头:4526731

    public static void posPrint(BinaryTreeNode root) {if (root != null) {posPrint(root.left);posPrint(root.right);System.err.print(root.val);}}

测试代码:

class BinaryTreeNode {int val;BinaryTreeNode left;BinaryTreeNode right;public BinaryTreeNode(int val) {this.val = val;}public BinaryTreeNode(int val, BinaryTreeNode left, BinaryTreeNode right) {this.val = val;this.left = left;this.right = right;}
}
    public static void main(String[] args) {BinaryTreeNode one = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(3, new BinaryTreeNode(6, null, null), new BinaryTreeNode(7, null, null)));prePrint(one);System.err.println();midPrint(one);System.err.println();posPrint(one);}

那么我们可以看出来,不论是哪种遍历方式,其在处理左右子节点的时候,逻辑都是一样的,都是要递归处理,不同的只是头结点的输出时机,那么可以优化成下面的代码:

    public static void print(BinaryTreeNode root, int type) {switch (type) {case 1:if (root != null) {System.err.print(root.val);print(root.left, 1);print(root.right, 1);}break;case 2:if (root != null) {print(root.left, 2);System.err.print(root.val);print(root.right, 2);}break;case 3:if (root != null) {print(root.left, 3);print(root.right, 3);System.err.print(root.val);}break;}}

2、两棵树是否结构一样

如下面的图中,只有左上角和右上角两棵树的结构是一样的,才算符合条件:

Java实现判断两棵树是否一样:

    public static boolean isSameTree(BinaryTreeNode node1, BinaryTreeNode node2) {if (node1 == null ^ node2 == null) {return false;}if (node1 == null && node2 == null) {return true;}return node1.val == node2.val && isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);}@Testpublic void testSame() {BinaryTreeNode one = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(3, new BinaryTreeNode(6, null, null), new BinaryTreeNode(7, null, null)));BinaryTreeNode two = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(3, new BinaryTreeNode(6, null, null), new BinaryTreeNode(7, null, null)));System.err.println(isSameTree(one, two));}

3、镜面树

镜面树有两种情况:

  1. 两棵树互为镜面:按照红线对折,可以重叠 
  2. 单棵树两边互为镜面:代码实现:
        public static boolean isMirror(BinaryTreeNode node1, BinaryTreeNode node2) {if (node1 == null ^ node2 == null) {return false;}if (node1 == null && node2 == null) {return true;}return node1.val == node2.val && isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);}@Testpublic void testMirror() {BinaryTreeNode one = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(2, new BinaryTreeNode(5, null, null), new BinaryTreeNode(4, null, null)));BinaryTreeNode two = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(2, new BinaryTreeNode(5, null, null), new BinaryTreeNode(4, null, null)));System.err.println(isMirror(one, two));}

 4、树的最大深度

二叉树的最大深度其实就是左子树和右子树的最大深度加一,代码实现如下:

    public static int maxDepth(BinaryTreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}@Testpublic void testMaxDepth() {BinaryTreeNode two = new BinaryTreeNode(1,new BinaryTreeNode(2, new BinaryTreeNode(4, null, null), new BinaryTreeNode(5, null, null)),new BinaryTreeNode(2, new BinaryTreeNode(5, null, null), new BinaryTreeNode(4, null, null)));System.err.println(maxDepth(two));}

5、还原二叉树

给定一个二叉树的前序遍历数组和中序遍历数组,两个数组中都没有重复值,根据这两个数组还原二叉树,返回头结点

解题思路:仍然是采用递归的方式,几个重要的解题点:

1、前序遍历的第一个元素一定是树的头结点,比如下面这个最基本的二叉树,前序遍历是1,2,3,中序遍历是2,1,3,所以树的头结点一定是1

2、找出中序遍历数组中头结点所在的位置,假设下标为A,那么在前序遍历数组中,从头结点所在下标加1到A(包括两端),以及在中序序遍历数组中从0到A减1(包括两端)的位置都是左子树的节点

比如下面这棵树的头结点是1,在中序遍历数组中的下标是1,那么2就是左子树,再比如文章最前面的第一棵二叉树,前序遍历1245367和中序遍历4251637,根据第二点我们可以得出前序遍历中的245和中序遍历中的425一定是左子树,右子树的逻辑也类似

 代码实现:

 public static BinaryTreeNode buildTree(int[] preorder, int[] inorder) {// 构建中序遍历数组中元素与索引的映射关系Map<Integer, Integer> inorderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inorderMap.put(inorder[i], i);}return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);}private static BinaryTreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderMap) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart];BinaryTreeNode root = new BinaryTreeNode(rootVal);if (preStart == preEnd) {//相等的时候说明要么是根节点,要么是到了最后一个节点return root;}int rootIndex = inorderMap.get(rootVal);int leftSize = rootIndex - inStart;root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize,inorder, inStart, rootIndex - 1, inorderMap);root.right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd,inorder, rootIndex + 1, inEnd, inorderMap);return root;}@Testpublic void testBuildTree() {int[] preorder = {1, 2, 4, 5, 3, 6, 7};int[] inorder = {4, 2, 5, 1, 6, 3, 7};
//        int[] preorder = {1, 2, 3};
//        int[] inorder = {2, 1, 3};BinaryTreeNode root = buildTree(preorder, inorder);print(root, 1);System.err.println();print(root, 2);System.err.println();print(root, 3);}

相关文章:

二叉树相关算法

1、二叉树基本操作 二叉树的定义就不在这里多说了&#xff0c;下面这个图就是一个简单的二叉树&#xff1a; 二叉树的三种遍历方式&#xff1a; 前序遍历&#xff1a;头左右&#xff0c;也就是先头后左再右&#xff1a;1245367 public static void prePrint(BinaryTreeNode …...

Vue_Bug npm install报错 code:128

Bug描述&#xff1a; npm install报错 code&#xff1a;128 npm ERR! Warning: Permanently added ‘github.com’ (ED25519) to the list of known hosts. npm ERR! gitgithub.com: Permission denied (publickey). npm ERR! fatal: Could not read from remote repository. n…...

【Unity ShaderGraph】| 如何快速制作一个 马赛克效果 实战

前言 【Unity ShaderGraph】| 如何快速制作一个 马赛克效果 实战一、效果展示二、马赛克效果四、应用实例 前言 本文将使用Unity 的ShaderGraph制作一个马赛克的效果&#xff0c;可以直接拿到项目中使用。对ShaderGraph还不了解的小伙伴可以参考这篇文章&#xff1a;【Unity S…...

【Java 进阶篇】JavaScript DOM Document对象详解

在前端开发中&#xff0c;DOM&#xff08;文档对象模型&#xff09;扮演着重要的角色。它允许我们使用JavaScript来与网页文档进行交互&#xff0c;实现动态的网页效果。DOM的核心部分之一就是Document对象&#xff0c;它代表了整个HTML文档。在本篇博客中&#xff0c;我们将深…...

LetCode刷题[简单题](5)按摩师,迭代出最优解(卡尔曼滤波也是类似迭代)

所有的遍历寻求有条件约束的最大值都可以转换成&#xff0c;新的数带来的最大值的变化&#xff0c;问题往这个方向转化就可以&#xff0c;问题都是在最中进行选择的&#xff0c;因此关注的问题最大值得上限就好了&#xff0c;不必关注可能随机的下限。关注随机可能的下限会把问…...

C/C++笔试易错与高频题型图解知识点(二)—— C++部分(持续更新中)

目录 1.构造函数初始化列表 1.1 构造函数初始化列表与函数体内初始化区别 1.2 必须在初始化列表初始化的成员 2 引用&引用与指针的区别 2.1 引用初始化以后不能被改变&#xff0c;指针可以改变所指的对象 2.2 引用和指针的区别 3 构造函数与析构函数系列题 3.1构造函数与析…...

使用new创建动态结构

在运行时创建数组优于在编译时创建数组&#xff0c;对于结构&#xff08;同一个结构可以存储多种类型的数据。&#xff09;也是如此。需要在程序运行时为结构分配所需的空间&#xff0c;这也可以使用new运算符来完成。通过使用new&#xff0c;可以创建动态结构。同样&#xff0…...

论文笔记与复现[156]PARAFAC. tutorial and applications

原文下载&#xff1a;https://www.sciencedirect.com/science/article/abs/pii/S0169743997000324 摘要 本文介绍了PARAFAC的多维分解方法及其在化学计量学中的应用。PARAFAC是PCA向高阶数组的推广&#xff0c;但该方法的一些特性与普通的二维情况截然不同。例如&#xff0c;…...

Python 基础30道测试题

你好&#xff0c;我是悦创。 我会给出 30 道涉及 Python 基础的题目。这些题目将覆盖各种 Python 基础知识点&#xff0c;包括数据类型、控制结构、函数、模块等。 输出 “Hello, World!”。创建一个变量&#xff0c;并为其赋值&#xff0c;然后输出该变量的值。输入两个数&a…...

【环境搭建】linux docker-compose安装rocketmq

创建目录 mkdir -p /data/docker/rocketmq/namesrv/logs mkdir -p /data/docker/rocketmq/broker1/conf mkdir -p /data/docker/rocketmq/broker1/logs mkdir -p /data/docker/rocketmq/broker1/store 给权限 chmod -R 777 /data/docker/rocketmq 创建配置文件 cd /data/d…...

python:使用卷积神经网络(CNN)进行回归预测

作者:CSDN @ _养乐多_ 本文详细记录了从Excel或者csv中读取用于训练卷积神经网络(CNN)模型的数据,包括多个自变量和1个因变量数据,以供卷积神经网络模型的训练。随后,我们将测试数据集应用于该CNN模型,进行回归预测和分析。 该代码进一步修改可用于遥感影像回归模型. …...

数据结构----算法--五大基本算法

数据结构----算法–五大基本算法 一.贪心算法 1.什么是贪心算法 在有多个选择的时候不考虑长远的情况&#xff0c;只考虑眼前的这一步&#xff0c;在眼前这一步选择当前的最好的方案 二.分治法 1.分治的概念 分治法&#xff1a;分而治之 将一个问题拆解成若干个解决方式…...

网格大师如何把b3dm转为osgb格式?

答&#xff1a;在网格大师的倾斜数据处理工具中选中“3DTiles转OSGB”&#xff0c;设定数据输入路径和输出路径提交任务即可。 网格大师是一款能够解决实景三维模型空间参考、原点、瓦块大小不统一&#xff0c;重叠区域处理问题的工具“百宝箱”&#xff0c;集格式转换、坐标转…...

基于深度优先搜索的图遍历

这里写目录标题 基于深度优先搜索的无向图遍历算法流程图Python实现Java实现 基于深度优先搜索的有向图遍历Python实现 基于深度优先搜索的无向图遍历 使用深度优先搜索遍历无向图&#xff0c;将无向图用邻接表存储&#xff1a; 算法流程图 初始化起点 source&#xff0c;当…...

Web3D虚拟人制作简明指南

如何在线创建虚拟人? 虚拟人,也称为数字化身、虚拟助理或虚拟代理,是一种可以通过各种在线平台与用户进行逼真交互的人工智能人。 在线创建虚拟人变得越来越流行,因为它为个人和企业带来了许多好处。 通过虚拟助理或代理,您可以以更具吸引力和个性化的方式与客户或受众进…...

【大数据 - Doris 实践】数据表的基本使用(一):基本概念、创建表

数据表的基本使用&#xff08;一&#xff09;&#xff1a;基本概念、创建表 1.创建用户和数据库2.Doris 中数据表的基本概念2.1 Row & Column2.2 Partition & Tablet 3.建表实操3.1 建表语法3.2 字段类型3.3 创建表3.3.1 Range Partition3.3.2 List Partition 1.创建用…...

剑指Offer || 038.每日温度

题目 请根据每日 气温 列表 temperatures &#xff0c;重新生成一个列表&#xff0c;要求其对应位置的输出为&#xff1a;要想观测到更高的气温&#xff0c;至少需要等待的天数。如果气温在这之后都不会升高&#xff0c;请在该位置用 0 来代替。 示例 1: 输入: temperatures…...

URL because the SSL module is not available

Could not fetch URL https://pypi.org/simple/pip/: There was a problem confirming the ssl certificate: HTTPSConnectionPool(host‘pypi.org’, port443): Max retries exceeded with url: /simple/pip/ (Caused by SSLError(“Can’t connect to HTT PS URL because the…...

excel 日期与时间戳的相互转换

1、日期转时间戳&#xff1a;B1INT((A1-70*365-19)*86400-8*3600)*1000 2、时间戳转日期&#xff1a;A1TEXT((B1/10008*3600)/8640070*36519,"yyyy-mm-dd hh:mm:ss") 以上为精确到毫秒&#xff0c;只精确到秒不需要乘或除1000。 使用以上方法可以进行excel中日期…...

MongoDB中的嵌套List操作

前言 MongoDB区别Mysql的地方&#xff0c;就是MongoDB支持文档嵌套&#xff0c;比如最近业务中就有一个在音频转写结果中进行对话场景&#xff0c;一个音频中对应多轮对话&#xff0c;这些音频数据和对话信息就存储在MongoDB中文档中。集合结构大致如下 {"_id":234…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

mac 安装homebrew (nvm 及git)

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

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...