Jianbo Dai's

jz026.树的子结构

 
  • Jun 01, 2020

题目链接

对于这道题目，我们可以将解决过程分成两步：第一步，在树A中找到和B的根节点的值，这节点标为R；第二步，当找到入口时，再判断树A中以R为根节点的子树是不是包含和树B一样的结构。对于第一步这一外层的递归，终止条件是走到两棵树的叶节点时。对于第二步这一内层的递归，当B被遍历完时则说明整棵树B都是A的子树，否则，当A提前被遍历完或者A和B的某个节点不同时，为False。这个算法的时间复杂度是O（NM），因为先遍历树A占用O（N），而每次调用recur占用O（M）。空间复杂度是O（N），因为当两棵树都退化为链表时，递归调用深度最大。当N<=M时，遍历树A与递归判断的总递归深度为N；当N>M时，最差情况为遍历至树A的叶节点，此时总递归深度为N。其中N为A中节点数量，M为B中节点数量。

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

class Solution:

    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        return self.recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

    def recur(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.recur(A.left, B.left) and self.recur(A.right, B.right)
Search