算法题合集

不做算法题的日子好无聊，有空就做做。

LeetCode 面试题 04.10. 检查子树

题意

判断A树中是不是包含B树。

思路

一开始考虑可以打印两棵树的序列，然后直接比对，后来发现序列打出来也比不了。接下来考虑对每个子树生成类似MD5的东西，一波dfs后直接判断MD5是否存在，但是网站上又用不了MD5的库，算了。但是我感觉我这个思路是可以的。

最后暴力去比对了，没啥意思。时间复杂度O(nm)。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import hashlib

class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not t1 or not t2:
            return False
        
        if t1 and t2:
            if t1.val == t2.val:
                if self.dfs(t1, t2):
                  return True
            
        if self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2):
            return True
        return False

    def dfs(self, t1, t2):
        if not t1 and not t2:
            return True
        
        if t1 and t2:
            if t1.val == t2.val:
                if not self.dfs(t1.left, t2.left):
                    return False
                if not self.dfs(t1.right, t2.right):
                    return False
                return True

        return False

Published on Jan 23, 2022 in categories