子结构判断

难度: Medium

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

提示：

0 <= 节点个数 <= 10000

Submission

运行时间: 128 ms

内存: 19.1 MB

# 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 B is None:
            return False
        if A is None:
            return False
        def dfs(p, q):
            if q is None:
                return True
            if p is None:
                return False
            return p.val == q.val and dfs(p.left, q.left) and dfs(p.right, q.right)
        return dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

Explain

这道题目要求判断二叉树B是否是二叉树A的一个子结构。解决这个问题的基本思想是使用递归。首先，如果B为空，根据题目定义，返回False。如果A为空，也返回False，因为空树不能包含非空子树。接下来，定义一个内部的辅助函数dfs来判断从某个节点开始的子树是否与B具有相同的结构和值。如果B的当前节点为空，说明B已经匹配完成，返回True；如果A的当前节点为空，而B不为空，返回False。如果两个节点值相等，递归地比较它们的左右子树。最后，递归地在A的左右子树中搜索是否存在与B结构相同的子树。

时间复杂度: O(M*N)

空间复杂度: O(h)

# 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:
        # 如果B为空，根据定义直接返回False
        if B is None:
            return False
        # 如果A为空，无法匹配非空B
        if A is None:
            return False
        # 定义dfs函数，检查以p为根的子树是否与q相同
        def dfs(p, q):
            # 如果q为空，说明B已经完全匹配
            if q is None:
                return True
            # 如果p为空，但q不为空，匹配失败
            if p is None:
                return False
            # 检查当前节点值是否相等，并递归检查左右子树
            return p.val == q.val and dfs(p.left, q.left) and dfs(p.right, q.right)
        # 检查当前节点开始的子树，或递归检查左右子树
        return dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

Explore

在算法的开始部分，通过检查`if B is None`来判断二叉树B是否为空。如果B为空，则函数返回False。这是因为，按照常规定义，空树不是任何树的子结构。子结构的含义通常要求至少有一个节点与主树的相应部分结构和值匹配。因此，一个空的二叉树B无法提供任何信息或结构以供比较，故不应被视为任何非空二叉树A的子结构。

递归函数dfs会在以下情况返回True：1) 当二叉树B的当前节点为空时，表示B的所有节点已经被成功匹配。2) 当二叉树A和B的当前节点值相等，并且A和B的左右子树也逐一匹配成功时。这确实意味着二叉树B的每个节点都必须与二叉树A的对应节点不仅值相等，而且结构相同，即B的每一个节点和它的子树都需要在A中找到完全一致的对应部分。

在dfs函数中，如果二叉树A的节点为空而二叉树B的节点不为空，函数返回False是因为这代表A已经没有更多节点可以用来与B的节点继续匹配。这确实考虑了所有可能的边界情况，因为一旦A的某个路径节点先耗尽，而B还有未匹配的节点，那么B不可能是A的子结构。

在主函数中递归检查A的左右子树是否包含B作为子结构，确实可能导致重复或不必要的计算，特别是当A的树结构较大或深度较深时。每次递归调用都会从A的一个子节点重新开始检查，可能会多次遍历A的同一部分。优化的方法可能包括使用额外的记忆化来存储已检查过的节点结果，或者在一些特定条件下剪枝，例如当已确定某一部分子树不可能包含B时，就不再继续在该部分子树中搜索。