二叉树的相关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。

相关文章

Java反射实现多属性去重与分组功能

Java反射实现多属性去重与分组功能

《Java反射实现多属性去重与分组功能》在Java开发中,​​List是一种非常常用的数据结构,通常我们会遇到这样的问题：如何处理​​List​​​中的相同字段？无论是去重还是分组,合理的操作可以提高... 目录一、开发环境与基础组件准备1.环境配置：2. 代码结构说明：二、基础反射工具：BeanUtils
阅读更多...
使用Python实现base64字符串与图片互转的详细步骤

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意
阅读更多...
使用Python实现获取屏幕像素颜色值

使用Python实现获取屏幕像素颜色值

《使用Python实现获取屏幕像素颜色值》这篇文章主要为大家详细介绍了如何使用Python实现获取屏幕像素颜色值,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、一个小工具，按住F10键，颜色值会跟着显示。完整代码import tkinter as tkimport pyau
阅读更多...
在Java中将XLS转换为XLSX的实现方案

在Java中将XLS转换为XLSX的实现方案

《在Java中将XLS转换为XLSX的实现方案》在本文中,我们将探讨传统ExcelXLS格式与现代XLSX格式的结构差异,并为Java开发者提供转换方案,通过了解底层原理、性能优势及实用工具,您将掌握... 目录为什么升级XLS到XLSX值得投入？实际转换过程解析推荐技术方案对比Apache POI实现编程
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
Java Lambda表达式的使用详解

Java Lambda表达式的使用详解

《JavaLambda表达式的使用详解》：本文主要介绍JavaLambda表达式的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、前言二、Lambda表达式概述1. 什么是Lambda表达式？三、Lambda表达式的语法规则1. 无参数的Lambda表
阅读更多...
java中Optional的核心用法和最佳实践

java中Optional的核心用法和最佳实践

《java中Optional的核心用法和最佳实践》Java8中Optional用于处理可能为null的值,减少空指针异常,：本文主要介绍java中Optional核心用法和最佳实践的相关资料,文中... 目录前言1. 创建 Optional 对象1.1 常规创建方式2. 访问 Optional 中的值2.1
阅读更多...
Spring Boot 整合 Apache Flink 的详细过程

Spring Boot 整合 Apache Flink 的详细过程

《SpringBoot整合ApacheFlink的详细过程》ApacheFlink是一个高性能的分布式流处理框架,而SpringBoot提供了快速构建企业级应用的能力,下面给大家介绍Spri... 目录Spring Boot 整合 Apache Flink 教程一、背景与目标二、环境准备三、创建项目 & 添
阅读更多...
Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析

Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析

《Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析》InstantiationAwareBeanPostProcessor是Spring... 目录一、什么是InstantiationAwareBeanPostProcessor？二、核心方法解
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2