二叉树另二叉树的子树
0x00 题目
给定两个非空
二叉树 s
和 t
检验 s
中是否包含和 t
具有相同结构和节点值的子树s
的一个子树包括 s
的一个节点和这个节点的所有子孙s
也可以看做它 自身
的一棵子树
0x01 思路
要有 相同的结构
以及 相同的值
就需要依次遍历 节点
与比较 值
通过 深度
优先搜索遍历 s
中的每一个节点
判断这个节点的 子树
是否和 t
相等
如何判断一个节点的子树是否和 t
相等呢?
就需要做一次 深度
优先搜索来检查
即让两个指针一开始先指向 该节点
和 t
的根
然后 同步移动
两根指针来 同步遍历
这两棵树
判断对应位置是否 相等
另外一种思路:
先将 t
树 前序
遍历序列化,序列化时需要记录 空
节点
然后 s
树 前序
遍历序列化,将每一次的序列结果和 t
的序列化结果进行判断,相等即包含
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 isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
// 对比检查
func check(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
// 都为空
if s == nil && t == nil { return true }
// 为空,或者值不相等
if (s != nil && t == nil) || (s == nil && t != nil) || (s!.val != t!.val) {
return false
}
// 继续检查子节点
return check(s!.left, t!.left) && check(s!.right, t!.right)
}
// 比较
func dfs(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
if s == nil { return false }
// 依次检查 根节点,左节点,右节点
return check(s, t) || dfs(s!.left, t) || dfs(s!.right, t)
}
return dfs(s, t)
}
方法 二
:
// 结果
var ans = false
// t 树转成的字符串
var tStr: String = ""
func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
// 先把 t 树转成的字符串
tStr = dfs(t, true)
// 在 s 树转成字符串的过程中,与 tStr 进行比较
_ = dfs(s, true)
// 最终结果
return ans
}
func dfs(_ root: TreeNode?, _ isLeft: Bool) -> String {
// 已经包含,加快退出
if ans { return "" }
// 当节点为空时,返回一个特殊的字符
guard let root = root else {
if isLeft {
return "L"
}
return "R"
}
// 在遍历左子树、右子树的同时,会与 tStr 进行比较
let str = "\(root.val)," dfs(root.left, true) dfs(root.right, false)
if str == tStr {
ans = true
}
return str
}
小笔记
让笔记一步到位~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgabafb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24