【二叉树】另一个二叉树的子树

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
}

---