【树】-Lc572-判断二叉树是否另一棵二叉树的子树(双层嵌套递归)

2024-03-08 16:04

本文主要是介绍【树】-Lc572-判断二叉树是否另一棵二叉树的子树(双层嵌套递归),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

写在前面

  最近想复习一下数据结构与算法相关的内容,找一些题来做一做。如有更好思路,欢迎指正。


目录

  • 写在前面
  • 一、场景描述
  • 二、具体步骤
    • 1.环境说明
    • 2.代码
  • 写在后面


一、场景描述

  给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false

二、具体步骤

1.环境说明

名称说明
IntelliJ IDEA2019.2

2.代码

以下为Java版本实现:

public class Lc572_isSubtree {public static void main(String[] args) {TreeNode s0 = new TreeNode(0);TreeNode s2 = new TreeNode(2);s2.right = s0;TreeNode s1 = new TreeNode(1);TreeNode s4 = new TreeNode(4);s4.left = s1;s4.right = s2;TreeNode s5 = new TreeNode(5);TreeNode s = new TreeNode(3);s.left = s4;s.right = s5;System.out.println("root is " + Helper.preOrderTraversal(s));TreeNode t2 = new TreeNode(2);TreeNode t1 = new TreeNode(1);TreeNode t = new TreeNode(4);t.left = t1;t.right = t2;System.out.println("subRoot is " + Helper.preOrderTraversal(t));System.out.println(isSubtree(s, t));}/*** 思路:** 要在s树中找和t树结点相同的结点** 首先要在s中找到和t结点相同的节点(s和t比,如果找不到,则需要s.left和t,s.right和t比),这是一个递归,结束条件是 if(s == null) return false* 第二个问题,比较(也是一个递归),结束条件是if(s==null && t==null) return true;*  剩下的条件分几种情况:*      其中有一个循环结束*      当前值不相同*      当前值相等,需要继续比较各自的左子树和右子树** @param s* @param t* @return*/private static boolean isSubtree(TreeNode s, TreeNode t) {// 递归结束条件if (s == null) {return false;}// 要在s中找到和t结点相同的节点// 如果当前2个结点不相等,那么就需要用s.left和t比,一直比到s.left=null(返回false)。还不相等,就用s.right和t比return check(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);}/*** 检查当前2个子树是否相同** 如果相等,(3)检查各自的左右子树结点,* 一直到(1)各自都是null(返回true)* (2)不等的情况:其中有一个为null或者2个值不相等(返回false)** @param s* @param t*/private static boolean check(TreeNode s, TreeNode t) {// 递归结束条件if (s == null && t == null) {return true;}if (s == null || t == null || s.val != t.val) {return false;}// s.val = t.valreturn check(s.left, t.left) && check(s.right, t.right);}static class Helper {private static List<Integer> preOrderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preOrder(root, result);return result;}private static void preOrder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preOrder(root.left, result);preOrder(root.right, result);}}static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}}

写在后面

  如果本文内容对您有价值或者有启发的话,欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。

这篇关于【树】-Lc572-判断二叉树是否另一棵二叉树的子树(双层嵌套递归)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/787625

相关文章

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

mysql递归查询语法WITH RECURSIVE的使用

《mysql递归查询语法WITHRECURSIVE的使用》本文主要介绍了mysql递归查询语法WITHRECURSIVE的使用,WITHRECURSIVE用于执行递归查询,特别适合处理层级结构或递归... 目录基本语法结构:关键部分解析:递归查询的工作流程:示例:员工与经理的层级关系解释:示例:树形结构的数

判断PyTorch是GPU版还是CPU版的方法小结

《判断PyTorch是GPU版还是CPU版的方法小结》PyTorch作为当前最流行的深度学习框架之一,支持在CPU和GPU(NVIDIACUDA)上运行,所以对于深度学习开发者来说,正确识别PyTor... 目录前言为什么需要区分GPU和CPU版本?性能差异硬件要求如何检查PyTorch版本?方法1:使用命

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用