652. Find Duplicate Subtrees

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

寻找重复subtree，粗暴的方法是遍历所有node，对于值相同的node，对比以该node为root的subtree是否相同。

换个思路的话，这题本质上还是遍历二叉树，应该还是二叉树搜索的递归模版可以解决的，此处改动就是，对left/right subtree的递归结果，要拿来验证是否已经出现过（即符合“重复“条件），有就加进结果。

# 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: TreeNode) -> List[TreeNode]:
        map_ = dict()
        res = []
        
        # 数组（子树）序列化
        def getId(root, map_, res):
            if not root: return "#"
            # 这里用前序/后续都可以，但中序不可以
            key = getId(root.left, map_, res) + "," + getId(root.right, map_, res) + "," + str(root.val)
            # 如果发现序列化了的subtree已经在map里了，就是有重复
            # 添加==1的判断，避免重复加入res
            if key in map_.keys() and map_[key] == 1: res.append(root)
            map_[key] = map_.get(key, 0) + 1
            return key
        
        getId(root, map_, res)
        return res