[剑指Offer] 26_树的子结构

题目

输入两棵二叉树A和B，判断B是不是A的子结构。

例：

           A                       B
            8                       8
    8              7             9     2
9       2
    4       7

A树中有一部分子树和B是一样的，因此B是A的子结构。

---

思路

1. 在A树中搜索和B树的root的val一样的节点，并从该节点向下逐个比对，如果B树遍历比对完成则表示是子结构，否则返回重新寻找root，直到A树遍历完毕。
   1. 时间复杂度：O(nlogn)，如果A树中除了最右节点其余全部节点都和B树的全部节点值相同，A、B一样高，将会T(n) = 2T(n/2) + O(n)
   2. 空间复杂度：O(logn)递归深度
2. 将A、B树的前序遍历缓存成字符串，比对B是否是A的子串，相同则表示匹配。比较是否字串使用in关键词，应该是O(n)。的因为B的大小是固定的，只要截取固定长度的字符串比较他们的哈希值 O(1)，比较n次即可。
   1. 时间复杂度：O(n)
   2. 空间复杂度：O(n)

---

代码

思路1：时间复杂度：O(nlogn)，空间复杂度：O(logn)

def substrucure_in_tree(main, sub):
    """    
    :param main: Big Tree 
    :param sub: substructure
    :return: bool
    """

    def compare(main_tree_sub, sub):
        """        
        :param main_tree_sub: node
        :param sub: substructure_root
        :return: bool
        """
        if not sub:
            return True
        if not main_tree_sub:
            return False
        if sub.val == main_tree_sub.val:
            return compare(main_tree_sub.left, sub.left) and compare(main_tree_sub.right, sub.right)
        return False

    if not main:
        return False
    if main.val == sub.val and compare(main, sub):
        return True
    else:
        return substrucure_in_tree(main.left, sub) or substrucure_in_tree(main.right, sub)
    return

思路2：时间复杂度：O(n) ，空间复杂度：O(n)

def substrucure_in_tree_2(main, sub):
    def preorder(root):
        return (root.val, preorder(root.left), preorder(root.right)) if root else None
    return str(preorder(sub)) in str(preorder(main))

---

思考

思路2是在LeetCode上看到的解法，相当于用空间换时间了。很有意思，代码很简洁。从另一个角度看，思路1对于极端情况重复比较和计算了很多次，所以思路2相当于添加了缓存，也就是备忘录法解决公共子问题，也是dp思想中的一点运用吧。
相似的题目，但是此题要求子孙节点严格相等，而不是覆盖。

LeetCode 572. 另一个树的子树

题目

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。