题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

解题思路

递归求解
二叉树就是递归结构，满足子树是子结构，则整个二叉树也是子结构

代码

class Solution:
    def subcheck(self, A, B):
        if not A:
            return False
        if A.val != B.val:
            return False
        if B.left:
            if not self.subcheck(A.left, B.left):
                return False
        if B.right:
            if not self.subcheck(A.right, B.right):
                return False
        return True


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