二叉树的相关oj题目 — java实现

2024-08-31 19:20
文章标签 java 二叉树 实现 题目 相关 oj

本文主要是介绍二叉树的相关oj题目 — java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的所有相关oj题

  • 题目
    • 翻转二叉树
    • 判断两颗树是否相同
    • 对称二叉树
    • 判断一棵二叉树是否为另一颗的子树
    • 平衡二叉树
      • 方法1：
      • 方法2：（更快）
    • 二叉树的层序遍历
    • 最近公共祖先
      • 方法1：
      • 方法2：
    • 二叉树的构建和遍历
    • 根据一棵树的前序遍历与中序遍历构造二叉树
      • 时间优化：
    • 根据一棵树的中序遍历与后序遍历构造二叉树
    • 根据二叉树创建字符串

题目

翻转二叉树

翻转二叉树

在这里插入图片描述

二叉树的问题一般都需要用到递归。

递归则需要我们将问题转换成子问题，并且需要一个结束条件

所以翻转整个二叉树有两个步骤：

  1. 先将 该树的左子树 和 右子树互换

在这里插入图片描述

  1. 递归翻转二叉树的左子树和右子树
    而结束条件是 一个树为一颗空树。

在这里插入图片描述
接下来只需要根据步骤来就可以了。

在这里插入图片描述

注意这里不是换 节点当中 的val，而是换整个节点。（也可以说是左子树和右子树互换）
在这里插入图片描述

最后翻转好了返回 root 即可。
在这里插入图片描述

最后这里也可以做个小优化，就是如果 这个树的左子树和右子树都是空树的话就可以直接 root，这样就不会进行 null 和 null 的无效交换

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}if (root.left == null && root.right == null) {return root;}// 节点互换TreeNode tmp = root.left;root.left = root.right;root.right = tmp;// 递归invertTree(root.left);invertTree(root.right);return root;}
}

判断两颗树是否相同

判断两颗树是否相同

还是利用递归来做

判断两颗树是否相同需要下面几个条件：

  1. 判断两棵树的根是否相同
  2. 递归判断左子树和右子树是否相同

只有都相同了，才能说明两树相同，只要有一处不相同，那么就不相同。

如果两树都是空树，那么两树一定是相等的。

在这里插入图片描述

如果两数当中仅有一树为空，那么两树一定不相等
在这里插入图片描述
此时，如果没有进入这两个 if 说明此时两树一定都不为空。

这个时候需要判断两树的根的值是否相等，如果不等，那么就直接说明两树不相等
在这里插入图片描述
最终就只需要满足一个条件那么两树就相等了，左子树和右子树都相等。
在这里插入图片描述
也可以优化写成这种。
在这里插入图片描述
前面的一处也可以进行优化
在这里插入图片描述
因为一旦前面的if 没有进去，那么两个树一定不都为空

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {// 两树都为空，则一定相等if (p == null && q == null) {return true;}// 两树仅有一个树为空，一定不相等if (p == null && q != null|| p != null && q == null) {return false;}// 两树的根节点的值不相同时，一定不相等if (p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

对称二叉树

判断是否是对称二叉树

这个题是没办法用一个函数去递归做的。

当一颗二叉树的左子树和右子树 互相是翻转二叉树，那么则可以说这棵树是对称二叉树

在这里插入图片描述
如果是空树，那么则是对称二叉树。

然后我们只需要返回 该树的左子树和右子树是不是翻转二叉树即可。

在这里插入图片描述
对于判断翻转二叉树函数来说，跟我们刚才的那道判断两树是否相等有点类似

只不过就是最后不一样，一个是左子树等于左子树，右子树等于右子树；
另一个左子树等于右子树，右子树等于左子树。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {//判断是否是对称二叉树public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return is(root.left, root.right);}//判断两颗树是否为翻转二叉树public boolean is(TreeNode p, TreeNode q) {//两树都为空，则是if (p == null && q == null) {return true;}//两树仅有一个为空树，则一定不是if (p == null || q == null) {return false;}//两树的根节点的值不相等，则一定不是if (p.val != q.val) {return false;}//只有p的左子树等于q的右子树//p的右子树等于左子树相等，说明为翻转二叉树，否则不是return is(p.left, q.right) && is(p.right, q.left);}
}

判断一棵二叉树是否为另一颗的子树

判断一颗二叉树是否为另一颗的子树

思路：

还是需要用到递归的思路。

当一棵树的与另一棵树相等或与其左子树或右子树相等时，就可以说，这棵树是另一颗树的子树。

首先我们要知道一个前提条件，当两棵树的任意一棵树如果为空树，那么就不是子树了。

在这里插入图片描述
这个也是我们的递归的结束条件。

这个题目要用到两棵树是否相等的函数，刚才我们已经写过了，所以直接拿来用。

在这里插入图片描述
然后我们只需要判断是不是满足下列要求当中的一个即可：

  1. 要么两树相等
  2. 要么左子树与另一棵树相等
  3. 要么右子树与另一棵树相等

在这里插入图片描述

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode p, TreeNode q) {if (p == null || q == null) {return false;}return isSameTree(p, q) || isSubtree(p.left, q) || isSubtree(p.right, q);}public boolean isSameTree(TreeNode p, TreeNode q) {
//1.先判断结构是否是一样的if(p != null && q == null || p == null && q != null) {return false;}
//上述if语句 如果没有执行，意味着两个引用 同时为空 或者同时不为空if(p == null && q == null) {return true;}
//都不为空 判断值是否一样if(p.val != q.val) {return false;}
//都不为空且值一样return isSameTree(p.left,q.left) &&  isSameTree(p.right,q.right);}
}

平衡二叉树

判断平衡二叉树

平衡二叉树是指的是所有节点的左子树和右子树的深度差不超过1.

方法1：

暴力获取每个节点的左子树和右子树的深度差。

在这里插入图片描述
注意每次需要特判 root是否为null，同时也是递归的结束条件

在这里插入图片描述
尽量不要函数套在函数里面，因为如果该函数得到的变量用到多次，那么就会重复进入函数，浪费时间，而且getHeight函数还是一个递归的函数

接着只需要写getHeight函数

一个树的高度等于，左子树的高度和右子树的高度的最大值 + 1

所以很好写

在这里插入图片描述

方法2：（更快）

方法1的时间复杂度有点高，遍历的每个节点都需要递归求该树的高度。

方法2思路：

在获取两颗子树的高度时顺便检查是否满足平衡二叉树

规定了如果返回的高度是-1则不满足条件，满足则返回该树的高度

判断左子树和右子树是否满足平衡二叉树，有一颗不满足，则直接不满足，两子树若都满足平衡二叉树，则判断两颗子树的深度差。

在这里插入图片描述

二叉树的层序遍历

二叉树的层序遍历

在这里插入图片描述
在进行特判时，不能返回null，需要返回一个空集合

这里的ArrayList集合也可以换成其他任意 实现List接口的集合

层序遍历有一个通用的模版

在这里插入图片描述

只需要将这个模版稍作修改即可

在这里插入图片描述

对于该题目来说，需要将每一层的所有节点的值存到集合当中

正常模版是每次弹出一个元素，但该题目需要每次弹出一整层的节点（正常模版也可以每次弹出一整层，都是一样的）

在这里插入图片描述

最后返回 ans 集合即可

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();//实现List接口的集合都可以if (root == null) {return res;//需要返回空集合而不是null}Queue<TreeNode> queue = new LinkedList<>();//实现Queue接口的集合都可以queue.offer(root);//将根节点入队列while (!queue.isEmpty()){//栈不为空List<Integer> list = new ArrayList<>();int size = queue.size();//该层的节点数while (size > 0) {//TreeNode top = queue.poll();list.add(top.val);if (top.left != null) {queue.offer(top.left);}if (top.right != null) {queue.offer(top.right);}size--;//*}res.add(list);}return res;}
}

最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

在这里插入图片描述

三个点代表可能存在某棵树，假设p 和 q 分别为所求公共祖先的两个节点，root为树的根节点

方法1：

思路是分情况后，利用递归解决

有下列几种情况

  1. 空树没有公共祖先

  2. 根节点为 p 或 q

在这里插入图片描述

假设根节点为 p节点时，共有三种情况，在左子树里、在右子树里或者在A 节点的上方（前提如果存在）

根节点为q节点 同理。

这种情况下，它们的最近的公共祖先就是 根节点 root

  1. 刚才的第2种情况已经考虑完所有关于根节点的情况，接下来的情况根节点不再跟p q有关，其中left 是左子树返回的节点，right同理
    在这里插入图片描述

代码如下：

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {//空树没有公共祖先return null;}if (root == p || root == q) {//先考虑根节点return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left == null) {return right;}if (right == null) {return left;}return root;}

方法2：

思路：

  1. 遍历所有节点，用哈希表存储 每个节点的父节点
  2. 从p节点往上遍历，把遍历的节点加到另一个哈希表里
  3. 此时向上遍历 q节点，如果 q节点在 哈希表当中存在，则该节点为最最近的公共祖先

 
本次需要用到的集合
在这里插入图片描述
 

第一步遍历我们可以用深度优先遍历（dfs），也可以想成子问题递归，由于有递归需要封装成一个函数

在这里插入图片描述

接着按照刚才的三个步骤即可

在这里插入图片描述
注意这里的while循环里 不是 q != root 和 p != root，而是 != null，如果是 != root，那么root不会放到hashSet集合里。

**当哈希表给一个不存在的值时会返回null，所以当放到 root的时候会返回null, 所以此时p == null会跳出循环

class Solution {Map<TreeNode, TreeNode> parent = new HashMap<>();//存储每个节点的父节点  Set<TreeNode> hashSet = new HashSet<>();//用于临时存储部分节点public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//1.将每个节点的父节点存储下来dfs(root);//2.将p节点的祖宗们放到另一个哈希表里while (p != null) {hashSet.add(p);p = parent.get(p);}//3.遍历q节点和他的祖宗们，出现的第一个重复的节点就是最近的公共祖先while (q != null) {if (hashSet.contains(q)) {return q;}q = parent.get(q);}//走到这里说明 q的祖宗们都不是 p 的祖宗们，所以没有公共祖先return null;}public void dfs(TreeNode root) {if (root == null) {//空树直接返回return;}if (root.left != null)  {parent.put(root.left, root);//root.left的父亲是rootdfs(root.left);}if (root.right != null) {parent.put(root.right, root);//root.right的父亲是rootdfs(root.right);}}
}

二叉树的构建和遍历

二叉树的构建

创建一个TreeNode类

主函数里只需要创建好树之后中序遍历即可
在这里插入图片描述
在这里插入图片描述

该题重点在于如何将先序遍历字符串变成一棵二叉树，就是createTree函数

大致思路：

  1. 需要一个下标 index 用于指向字符串中的字符
  2. 创建一个节点，节点的值为 字符串中 index下标的值
  3. 子问题递归，该节点的左子树和右子树则等于 index++时的函数

在这里插入图片描述

根据一棵树的前序遍历与中序遍历构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树

知识点：

  1. 前序遍历的遍历优先度是 根 > 左 > 右，本题中我们需要从头开始把前序遍历的数字按个当成根
  2. 在中序遍历中，遍历优先度是 左 > 根 > 右，一个节点的左边的节点，一定在他的左子树里，右边的节点同理在这里插入图片描述
    比如节点4的左边节点，那么就一定都在4节点的左子树里，右边的节点都在右子树里

大致思路：

  1. 需要一个下标变量指向中序遍历的数组，记为preindex
  2. 创建值为 preorder[preindex]的节点，作为整棵树的根节点
  3. 找到该 根节点在中序遍历序列的位置
  4. 递归处理

在这里插入图片描述

由于递归的时候需要给一个inorder数组的序列范围，所以需要另写一个函数

在这里插入图片描述

注意事项：
preindex 不放在函数的参数里，因为这样递归在归的时候，preindex就会还原，而正确情况应该是下标从0开始一直到数组inorder 的结尾下标

preindex需要放在外面当做成员变量，注意这里的preIndex 不要用 static 修饰，因为静态变量只要类被加载了，那么就会一直存在，所以第二个测试用例对象及以后的 preIndex的值 不等于0
 

先递归左子树，再递归右子树，因为前序遍历的优先度是 根 左 右。

在这里插入图片描述

时间优化：

find函数需要遍历完 下标 inst 到 ined，每次都需要遍历一遍非常耗时间，所以我们可以将中序遍历的值和下标的对应关系存起来

我们可以利用HashMap存储对应 关系

在这里插入图片描述

接下来只需要将 init 函数放在最初的函数中，并且把find 函数替换掉即可

在这里插入图片描述

在这里插入图片描述

public Map<Integer, Integer> relation = new HashMap<>();public void init(int[] inorder) {for (int i = 0; i < inorder.length; i++) {relation.put(inorder[i], i);}}public TreeNode buildTree(int[] preorder, int[] inorder) {init();return bulidTreeChild(preorder, inorder, 0, inorder.length - 1);}public int preIndex = 0;//前序遍历中的即将作为根节点的下标，可以不赋值，默认是0  // 返回数组下标从 inst 到 ined 的中序遍历 所构成的二叉树public TreeNode bulidTreeChild(int[] preorder, int[] inorder, int inst, int ined) {if (inst > ined) {//递归的结束条件return null;}//创建根节点TreeNode root = new TreeNode(preorder[preIndex]);//rootIndex是根节点在中序遍历里的下标int rootIndex = relation.get(root.val);//也可以写preorder[preIndex]preIndex++;//用一个根节点后 下标++;//根节点的左子树和右子树 子递归实现root.left = bulidTreeChild(preorder, inorder, inst, rootIndex-1);root.right = bulidTreeChild(preorder, inorder, rootIndex+1, ined);return root;}//找对应节点的下标public int find(int[] inorder, int inst, int ined, int val) {for (int i = inst; i <= ined; i++) {if (inorder[i] == val) {return i;}}return -1;}

根据一棵树的中序遍历与后序遍历构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树

本题大致思路和刚才的前序中序遍历构造二叉树差不多

后序遍历的序列的最后一个值 是 整棵树的根节点

大致思路：

  1. 定义一个变量postIndex 指向 postorder数组的最后一个元素
  2. 创建一个值为postorder[postIndex]的节点作为根节点
  3. 找到该节点在中序遍历序列中的位置，postIndex–;
  4. 递归，并且是先递归右子树，再左子树，因为后序遍历的优先度是左右根，由于postindex是从大到小遍历的，所以右的优先度比左高，所以先递归左子树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

根据二叉树创建字符串

根据二叉树创建字符串

大致思路：

  1. 在所给函数中创建一个StringBuilder对象记为sb，另写一个需要递归的函数并且参数中含有该对象，最后返回调用该对象的toString的值即可
  2. 将根节点的值拼接到sb，利用递归将左子树和右子树进行拼接

在这里插入图片描述
在这里插入图片描述

完

这篇关于二叉树的相关oj题目 — java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1124776。

相关文章

springboot的调度服务与异步服务使用详解

springboot的调度服务与异步服务使用详解

《springboot的调度服务与异步服务使用详解》本文主要介绍了Java的ScheduledExecutorService接口和SpringBoot中如何使用调度线程池,包括核心参数、创建方式、自定... 目录1.调度服务1.1.JDK之ScheduledExecutorService1.2.spring
阅读更多...
将java程序打包成可执行文件的实现方式

将java程序打包成可执行文件的实现方式

《将java程序打包成可执行文件的实现方式》本文介绍了将Java程序打包成可执行文件的三种方法：手动打包（将编译后的代码及JRE运行环境一起打包）,使用第三方打包工具（如Launch4j）和JDK自带... 目录1.问题提出2.如何将Java程序打包成可执行文件2.1将编译后的代码及jre运行环境一起打包2
阅读更多...
Java使用Tesseract-OCR实战教程

Java使用Tesseract-OCR实战教程

《Java使用Tesseract-OCR实战教程》本文介绍了如何在Java中使用Tesseract-OCR进行文本提取,包括Tesseract-OCR的安装、中文训练库的配置、依赖库的引入以及具体的代... 目录Java使用Tesseract-OCRTesseract-OCR安装配置中文训练库引入依赖代码实
阅读更多...
Java中对象的创建和销毁过程详析

Java中对象的创建和销毁过程详析

《Java中对象的创建和销毁过程详析》：本文主要介绍Java中对象的创建和销毁过程,对象的创建过程包括类加载检查、内存分配、初始化零值内存、设置对象头和执行init方法,对象的销毁过程由垃圾回收机... 目录前言对象的创建过程1. 类加载检查2China编程. 分配内存3. 初始化零值4. 设置对象头5. 执行
阅读更多...
SpringBoot整合easy-es的详细过程

SpringBoot整合easy-es的详细过程

《SpringBoot整合easy-es的详细过程》本文介绍了EasyES,一个基于Elasticsearch的ORM框架,旨在简化开发流程并提高效率,EasyES支持SpringBoot框架,并提供... 目录一、easy-es简介二、实现基于Spring Boot框架的应用程序代码1.添加相关依赖2.添
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程

SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程

《SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程》本文详细介绍了如何在虚拟机和宝塔面板中安装RabbitMQ,并使用Java代码实现消息的发送和接收,通过异步通讯,可以优化... 目录一、RabbitMQ安装二、启动RabbitMQ三、javascript编写Java代码1、引入
阅读更多...
MySQL8.0设置redo缓存大小的实现

MySQL8.0设置redo缓存大小的实现

《MySQL8.0设置redo缓存大小的实现》本文主要在MySQL8.0.30及之后版本中使用innodb_redo_log_capacity参数在线更改redo缓存文件大小,下面就来介绍一下,具有一... mysql 8.0.30及之后版本可以使用innodb_redo_log_capacity参数来更改
阅读更多...
spring-boot-starter-thymeleaf加载外部html文件方式

spring-boot-starter-thymeleaf加载外部html文件方式

《spring-boot-starter-thymeleaf加载外部html文件方式》本文介绍了在SpringMVC中使用Thymeleaf模板引擎加载外部HTML文件的方法,以及在SpringBoo... 目录1.Thymeleaf介绍2.springboot使用thymeleaf2.1.引入spring
阅读更多...
C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2