当前位置: 首页 > news >正文

子结构判断

子结构判断

LCR 143. 子结构判断

参考题解

题前知识

1)子结构

首先我们先了解一下子结构:

  • 原题信息:判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值
  • 子结构也就是B树是否含于A树左子树或者右子树之中,并且具有相同的结构和节点值,或者是否以A树的根节点作为子树

2)先序遍历

该题使用到了先序遍历,先序遍历相关代码

先序遍历规则:根左右

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();dfs(res, root);return res;
}
private void dfs(List<Integer> res, TreeNode root){if(root == null){return;}res.add(root.val);dfs(res, root.left);dfs(res, root.right);}

正题

我们可以使用先序遍历A的每个节点,然后我们判断A树是否包含B

由于我们判断A树是否包含B树是从根节点开始匹配的,所以先序遍历的更合适本题

判断A树是否包含B

终止条件

  • B为空,说明B已经匹配完成,返回true;
  • A为空,匹配失败,B树已经越过了A的叶子结点,超出范围了,返回false;
  • A的节点值和B的节点值不一样,返回false

返回条件

  • 判断A的左节点是否和B的左节点相等 –> recur(A.left, B.left)
  • 判断A的右节点是否和B的右节点相等 –> recur(A.right, B.right)
public boolean recur(TreeNode A, TreeNode B) {if(B == null) return true;if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);
}

isSubStructure(A, B)函数

边界条件

  • A树或者B树为null,返回false

三种情况

  • A的根节点为子树包含B
  • A的左子树为子树包含B
  • A的右子树为子树包含B

以上情况只要符合一种就返回true

最终代码:

通过recur(A, B)找到B的根节点和B的子节点是否和A的匹配

public boolean isSubStructure(TreeNode A, TreeNode B) {return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}public boolean recur(TreeNode A, TreeNode B) {if(B == null) return true;if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);
}

题后解析

关于题中用到的先序遍历思想

1、isSubStructure(A, B)中的先序遍历

对于树A的某个节点:

  1. 先访问根节点:执行 recur(A, B) 检查当前节点是否能作为匹配的起点
  2. 再遍历左子树:如果根节点不匹配,递归调用 isSubStructure(A.left, B)
  3. 最后遍历右子树:如果左子树也没有找到,递归调用 isSubStructure(A.right, B)

2、recur 方法中的先序遍历

  • 先比较当前根节点的值 (A.val != B.val)
  • 再递归比较左子树 (recur(A.left, B.left))
  • 最后递归比较右子树 (recur(A.right, B.right))
http://www.hskmm.com/?act=detail&tid=22626

相关文章:

  • 使用 Go 进行验证码识别
  • 使用 Rust 进行验证码识别
  • 使用 Swift 进行验证码识别
  • torchtext与torch版本对应关系
  • Python错题集
  • 火狐浏览器新页覆盖旧页解决方法
  • msi主板,windows11,mbr转gpt后,提示0xc000000e1,无法进入系统
  • MAUI下热重载不生效
  • AdGuard广告拦截器APP v4.11.63 / 4.13.7 Nightly 修改版
  • 在疼痛中锚定前路
  • Chrome在Android上Speedometer性能翻倍的技术揭秘
  • 《电路基础》第四章学习笔记
  • 题解:AT_arc184_d [ARC184D] Erase Balls 2D
  • US$39 PowerBox for KTM JTAG for Hitachi
  • 最小二乘问题详解2:线性最小二乘求解
  • OpenAI炸场!Sora 2正式发布,它不只是个视频模型,更是一个社交宇宙!
  • 基于python资料挖据的教学监控系统的设计与应用
  • 2025防腐木厂家权威推荐榜:实力品牌与定制服务深度解析
  • 中间件详解与自定义 - 实践
  • 格林达姆 花——季护航2006年-2017年天朝纸媒资料备份(不全)
  • 【Groovy】变量和基本数据类型
  • 2026届模拟/射频IC设计方向保研经验分享
  • 2021 ICPC 沈阳 BEFHJLM(待补
  • Docker容器完全操控指南
  • 【Groovy】Groovy环境搭建
  • 2025年TAB拉链制造商权威推荐榜:创新设计与耐用品质口碑
  • 变量类型
  • 10.1
  • VMware Cloud Foundation 9.0.1.0 发布 - 领先的多云平台
  • velero 备份及使用方法