难度: Medium
检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
注意：此题相对书上原题略有改动。
示例1:
输入：t1 = [1, 2, 3], t2 = [2] 输出：true
示例2:
输入：t1 = [1, null, 2, 4], t2 = [3, 2] 输出：false
提示：
运行时间: 48 ms
内存: 23.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 isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
if not t1:
return False
if self.isSameTree(t1, t2):
return True
return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)
此题解主要采用递归方法来确定T2是否为T1的子树。首先定义一个辅助函数isSameTree，用于判断两棵树是否完全相同。然后在主函数checkSubTree中，对T1进行递归遍历，在每个节点处调用isSameTree来检查该节点生成的子树是否与T2相同。如果在任何节点发现T2为子树，则立即返回true。如果遍历完整个树也没有发现，则返回false。
时间复杂度: O(n*m)
空间复杂度: O(log n) in best case, O(n) in worst case
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, s, t):
# 如果两棵树都为空，则它们相同
if not s and not t:
return True
# 如果其中一棵树为空，则它们不相同
if not s or not t:
return False
# 检查当前节点的值以及左右子树是否相同
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
# 如果T1为空，直接返回False
if not t1:
return False
# 检查当前节点形成的树是否与T2相同
if self.isSameTree(t1, t2):
return True
# 递归检查左右子树
return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)
在理论上，空树是任何树的子树，因此如果T2为空树，根据常见的定义，我们应该将T2视为T1的子树。然而，题解中并没有显式处理T2为空的情况，这可能会导致在T2为空时，解决方案返回False。为了符合常规定义，应该在checkSubTree方法开始时加入：如果t2为空，则返回True。这样的处理更合乎逻辑和数学定义，即空树被认为是任何树的子树。
在题解的checkSubTree方法中，即使当前节点的子树与T2不相同（即isSameTree返回False），算法仍继续在T1的左子树和右子树中递归寻找T2。这通过在checkSubTree中调用自身来实现：`return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)`。这确保了算法会在T1的所有可能的位置继续寻找T2，不仅限于值相同的节点。
在T1和T2节点数极度不平衡的情况下，当前的递归遍历可能会导致大量不必要的比较，尤其是当T1很大而T2很小的时候。一种可能的优化方法是使用更高效的匹配算法，如基于哈希的树同构算法（如Merkle哈希）。在这种方法中，可以为T1的每个子树计算一个哈希值，并存储在哈希表中，然后计算T2的哈希值并在哈希表中查找是否存在。这种方法可以显著减少必要的比较次数，特别是对于大树结构。此外，还可以在遍历T1时剪枝，例如如果某个子树的节点数少于T2的节点数，则无需检查该子树。