LeetCode 572.另一棵树的子树代码报错，请求排查问题

题目描述 #

给定两棵二叉树的根节点root和subRoot，若root中存在子树的结构与节点值和subRoot完全一致，返回true，否则返回false。二叉树的子树指由某节点及其所有后代组成的树，树本身也视为自身的子树。

示例1 #

Input:  root = [3,4,5,1,2], subRoot = [4,1,2]
Output:  true

示例2 #

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

我的代码 #

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        if not root and not subRoot:
            return True
        if root==None or subRoot==None:
            return False
        
        if root.val == subRoot.val and self.isSubtree(root.left,subRoot.left) and self.isSubtree(root.right,subRoot.right):
            return True
        
        return self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)

失败案例 #

Input
[3,4,5,1,null,2]
[3,1,2]

Output  True

Expected  False

问题分析与修复 #

你的代码核心错误在于：把「判断两棵树是否完全相等」和「查找子树」的逻辑混在了同一个函数里。

当root.val == subRoot.val时，你调用isSubtree(root.left, subRoot.left)，但这个函数的逻辑是「在root.left中找subRoot.left作为子树」，而不是「判断root.left和subRoot.left是否完全相等」。比如在失败案例中：

• root根节点是3，subRoot根节点也是3，进入判断分支
• 递归判断左子树：root.left是4，subRoot.left是1，此时isSubtree(4,1)会继续在4的子树里找1，刚好4的左孩子就是1，返回true
• 递归判断右子树：root.right是5，subRoot.right是2，isSubtree(5,2)会在5的子树里找2，5的右孩子就是2，返回true
• 最终错误返回true，但实际上root的根节点对应的树和subRoot完全不一样

修复方案是拆分出一个单独的isSameTree函数，专门判断两棵树是否完全相等：

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        # 先判断当前节点对应的树是否和subRoot完全相等
        if self.isSameTree(root, subRoot):
            return True
        # 不相等的话，继续在左右子树里找
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

这个修复后的逻辑：

1. isSameTree严格判断两棵树的结构和节点值完全一致
2. isSubtree先检查当前节点是否能和subRoot匹配，不匹配则递归遍历左右子树继续查找

内容的提问来源于stack exchange，提问作者Vishav Singla