Day 27：572. Subtree of Another Tree

今日题目

题目连结：572. Subtree of Another Tree
题目主题：Tree, Depth-First Search, String Mathcing, Binary Tree, Hash Function

讲完几个常见的演算法主题以後，这两天会开始分享 Hash 相关的主题。

简单说说 Hash Function

我认为 Hash 的核心概念是简化一个复杂的资料，让资料有更好的效能处理问题，这个简化不管是将资料变成数字或是字串都是有可能的。

另外有两个重点：

• Hash 过後得到的值是有可能遇到碰撞的问题，也就是说两个不一样的资料 Hash 过後却得到相同的值，这样就是所谓的碰撞，在设计 Hash Function 时需要特别小心。
• Hash 过後得到的值，在不知道 Hash Function 逻辑的状况下，理论上是很难推回到原本资料的长相。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给两个 Binary Tree 分别为 root 及 subRoot，如果 subRoot 有出现在 root 之中并且结构及节点值都相同，回传 True，不符合条件回传 False。

约束：

• root 的节点总数范围在[1, 2000].
• subRoot 的节点总数范围在 [1, 1000].
• -10的4次方 <= root.val <= 10的4次方
• -10的4次方 <= subRoot.val <= 10的4次方

范例1

输入: root = [3,4,5,1,2], subRoot = [4,1,2]
输出: true
解说: 上图是LeetCode提供的范例图，很明显可以看到 subRoot 有出现在 root 里面且结构及节点值都相同。

范例2

输入: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出: false
解说: 上图是LeetCode提供的范例图，虽然看得到 [4, 1, 2] 有出现在 root 之中，但最终输出为 false 的原因是 2 节点的结构并不相同，root 这边多 2 出现了子节点。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个方法将树转成字串。
2. 将题目给的 root 及 subRoot 转成字串。
3. 若 subRoot 的字串有出现在 root 的字串中，代表这颗 subRoot 的树有出现在 root 中，回True，相反的没出现就回 False。

图解过程

范例:
root = [5, 4, 1, 7, 2]
subRoot = [4, 7, 2]

上图是过程中，分别会先将 root 及 subRoot 这两个复杂的树简化成一个字串，之後便可以直接用这两个字串比对出subRoot 是否有出现在 root 中，以这个范例来说是有比对到 subRoot 转成的字串是有出现在 root 字串之中的红色底线部份，因此会回传 True。

这个树转换成字串的过程，是运用了Preorder、Inorder、Postorder的方式组成的字串，每个数字至少会被经过三次，这样可以确认到结构的长相。

上图中，黑色数字是Preorder经过时纪录的、红色数字是Inorder经过时纪录的、绿色数字就是Postorder经过的，这样转换出来的字串便可完整的去确认 root 中是否有出现跟 subRoot 结构及节点值都相同的树。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def convertString(self, root, rootStr = ''):
        if root == None: return rootStr
        
        rootStr += str(root.val)
        rootStr = self.convertString(root.left, rootStr)
        rootStr += str(root.val)
        rootStr = self.convertString(root.right, rootStr)
        rootStr += str(root.val)
        
        return rootStr
        
    
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        subRootStr = self.convertString(subRoot)
        rootStr = self.convertString(root)
        
        return subRootStr in rootStr

希望您今天能了解到...

1. Hash Function 的基本概念
2. 572. Subtree of Another Tree 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：1. Two Sum