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

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2