二叉树的所有相关oj题目 — java实现（持续更新）

2024-09-01 16:36
文章标签 java 二叉树 实现 题目 更新 所有 相关 持续 oj

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

二叉树的所有相关oj题

  • 题目
    • 翻转二叉树
    • 判断两颗树是否相同
    • 对称二叉树
    • 判断一棵二叉树是否为另一颗的子树
    • 平衡二叉树
      • 方法1：
      • 方法2：（更快）
    • 二叉树的层序遍历
    • 二叉树的层序遍历II
    • 最近公共祖先
      • 方法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;}
}

二叉树的层序遍历II

二叉树的层序遍历II

相较于自底向上的层序遍历，只需要每次将整层节点 头插到最终的 List集合即可

在这里插入图片描述

最近公共祖先

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

在这里插入图片描述

三个点代表可能存在某棵树，假设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/1127477。

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
Java编译生成多个.class文件的原理和作用

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类（常规内部类）局部内部类（方法内部类）匿名内部类二、
阅读更多...
SpringBoot实现数据库读写分离的3种方法小结

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一：基于AbstractRoutingDataSource实现动态
阅读更多...
Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整
阅读更多...
Springboot @Autowired和@Resource的区别解析

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@
阅读更多...
springboot循环依赖问题案例代码及解决办法

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖（即BeanA依赖BeanB,而BeanB又依赖BeanA）,会导致Spring的... 目录1. 什么是循环依赖？2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1：使用 @La
阅读更多...
Java枚举类实现Key-Value映射的多种实现方式

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co
阅读更多...
使用Python实现快速搭建本地HTTP服务器

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》：本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.
阅读更多...
Elasticsearch 在 Java 中的使用教程

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J
阅读更多...
Java中的String.valueOf()和toString()方法区别小结

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2