LeetCode652寻找重复子树Python实现问题排查与修正咨询

• 1. isSameSubtree方法逻辑存在两处致命错误：
     首先空节点判断逻辑错误：当两个节点一个为空一个不为空时应该返回False，你写的if left is None or right is None: return True完全不符合相等判断规则；其次两棵树相等需要左右子树都相等，你用了or逻辑，只要任意一边相等就返回真，完全偏离相等判断要求。
• 2. 整体遍历思路错误：你只比对了同一个父节点的左右子树，而重复子树完全可能分布在整棵树的不同分支下，不属于同一个父节点，这种情况你的逻辑完全无法检测到。
• 3. helper方法返回逻辑不完整：只有当左右子树相等时才有返回值，其余分支无返回，上层递归拿到的节点值会出现非预期的空值，逻辑完全混乱。

我们采用序列化子树+哈希计数的思路实现：将每个节点作为根的子树序列化成唯一字符串，用哈希表统计每个序列化字符串出现的次数，当某字符串第二次出现时，就将对应的根节点加入结果集，保证同一类重复子树只被加入一次。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        count = {}
        res = []
        
        def serialize(node):
            if not node:
                return "#"
            # 生成当前子树的序列化标识，用分隔符避免不同结构生成相同字符串
            serial = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            count[serial] = count.get(serial, 0) + 1
            # 第二次出现时加入结果，避免重复添加
            if count[serial] == 2:
                res.append(node)
            return serial
        
        serialize(root)
        return res

内容的提问来源于stack exchange，提问作者Michael Torres