当前位置:网站首页>【二叉树】树的子结构
【二叉树】树的子结构
2022-08-09 18:42:00 【豪冷啊】
0x00 题目
输入两棵二叉树A
和B
,判断B
是不是A
的子结构
约定空树
不是任意一个树的子结构
B
是A
的子结构
即 A
中有出现和 B
相同的结构和节点值
0x01 思路
若树 B
是树 A
的子结构
则子结构的根节点可能为树 A
的任意一个节点
所以要遍历 A
树的每个节点
依次与 B
的每个节点进行比较
当节点 B
为空:说明树 B
已匹配完成(越过叶子节点),因此返回 true
当节点 A
为空:说明已经越过树 A
叶子节点,即匹配失败,返回 false
当节点 A
和 B
的值不同:说明匹配失败,返回 false
0x02 解法
语言:Swift
树节点:TreeNode
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
解法:
func isSubStructure(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
func dfs(_ a: TreeNode?, _ b: TreeNode?) -> Bool {
if b == nil { return true } // B 到头了
if a == nil { return false } // A 到头了
if a!.val != b!.val { return false } // 值不相等
return dfs(a?.left, b?.left) && dfs(a?.right, b?.right)
}
guard let _ = A else { return false }
guard let _ = B else { return false }
let b1 = dfs(A, B)
let b2 = isSubStructure(A?.left, B)
let b3 = isSubStructure(A?.right, B)
return b1 || b2 || b3
}
0x03 我的小作品
欢迎体验我的作品之一:小五笔 86 版
五笔学习好帮手~App Store
搜索即可~
边栏推荐
- mysql duplicate data group multiple latest records
- Office 365 Group概述以及创建方法
- 三星旗舰优惠千八,苹果优惠过千,国产旗舰只降五百打发叫花子
- [免费专栏] Android安全之安卓APK浅析
- 再次开始清理电子海图开发群中长期潜水人士
- [免费专栏] Android安全之ZIP文件目录遍历漏洞
- IS31FL3737B general 12 x 12 LED drive 40 QFN I2C 42 ma
- From functional testing to automated testing, do you know their shortcomings?
- 听音识情绪 | 程序员手把手教你搭建神经网络,更快get女朋友情绪,求生欲max!
- Swift--多条件排序
猜你喜欢
How to stop the test after reaching a given number of errors during stress testing in JMeter
shell之变量详解,让你秒懂!
[免费专栏] Android安全之GDB动态调试APP
2021 RoboCom 世界机器人开发者大赛-本科组(决赛)
2022深圳(软考高级)信息系统项目管理师认证报名
数学建模——模拟退火
[Free Column] Android Security for Peace Elite (FZ) APK Reverse Analysis
IDEA tools commonly used configuration
[免费专栏] Android安全之和平精英(FZ)APK逆向分析
为什么数字钱包需要引入小程序生态
随机推荐
[免费专栏] Android安全之Android奇淫run-as命令
【Unity3D】2D动画
华为云全流程护航《流浪方舟》破竹首发,打造口碑爆款
MYSQL物理存储文件的页和INNOBUF的页是否有大小区别?
面试官:MySQL 中 update 更新,数据与原数据相同时会执行吗?大部分人答不上来!
Iptables防火墙常见的典型应用场景
[免费专栏] Android安全之GDB动态调试APP
Qt 5.12 LTS 部署
How to suppress alarm storms?
IDEA快捷代码实时模板
MFC tutorial
php安装make出现“collect2:error:ldreturned1exitstatus
工大科雅深交所上市:市值45亿 齐承英家族是大股东
漏洞复现-redis未授权getshell
安装多版本php(php5.6,php7.2)
Leetcode 739.每日温度 单调栈
嵌入式开发:使用FILL提高代码完整性
一图详解沃土云创计划高校教师参与全流程
laravel 时区问题timezone
Environment: Flink version: 1.15.1 jar package: flink-sql-connector-oracle