题解 | #树的子结构#
树的子结构
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))
