题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
python3,递归方法。
子结构内的递归:子结构,意味着从头到子树递归的匹配上。
如果子结构递归到空,即意味着完成了全部匹配,返回True。如果子结构没递归到空且这时树递归到空了,即意味着不够匹配,返回False;或者结点不相等,匹配失败,返回False。
子结构头的递归:如果以当前树结点作为子结构的头,匹配不上,这个头也要在树内递归的变化。
如果子结构是空树,直接返回False,如果子结构的头(树结点)是空,不够匹配,返回False。如果树当前结点作为头,递归成功,则返回True;或者换头之后匹配成功,也返回True,用or连接这个递归。
class Solution: # 头本身也要递归 def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool: def dfs(h1, h2): # 从头递归判断 if not h2: return True if not h1 or h1.val != h2.val: return False return dfs(h1.left, h2.left) and dfs(h1.right, h2.right) return bool(pRoot1 and pRoot2) and (dfs(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2))