【LeetCode 二叉树专项】寻找重复的子树（652）

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一
  • • 2.1 分析
    • 2.2 实现
    • 2.3 复杂度

1. 题目

给定一棵二叉树的根节点，请返回所有的重复子树。对于每一类重复子树，你只需要返回其中任意一个的根节点即可。如果两棵二叉树拥有相同的结构和节点值，则称这两棵二叉树是重复的。

1.1 示例

• 示例 $1$ ：

  • 输入： root = [1, 2, 3, 4, null, 2, 4, null, null, 4]
  • 输出： [[2, 4], [4]]

• 示例 $2$ ：

  • 输入： root = [2, 1, 1]
  • 输出： [[1]]

• 示例 $3$ ：

  • 输入： root = [2, 2, 2, 3, null, 3, null]
  • 输出： [[2, 3], [3]]

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/find-duplicate-subtrees

1.3 限制

• 二叉树中的节点数量在 $[1,10^4]$ 之间；
• -200 <= Node.val <= 200 。

2. 解法一

2.1 分析

想要正确解答本题，只需要知道如何给出二叉树的某种唯一性表达即可，接下来首先获得以给定二叉树的所有节点为根节点的子二叉树的表达形式，然后得到所有重复表达形式对应子树的根节点即可。

实际上，所谓给出二叉树的某种唯一表达其实就是对二叉树进行序列化，而在【LeetCode 二叉树专项】二叉树的序列化与反序列化（297）中，我们给出了基于二叉树深度优先搜索（前序遍历、后序遍历）以及广度优先搜索实现的二叉树序列化。

接下来，需要确定就是具体采用哪种方式序列化。本题采用二叉树的后序遍历对给定二叉树的所有子树进行序列化。

2.2 实现

from json import dumpsfrom typing import Optional, List, Set, Dict, Unionclass TreeNode:    def __init__(self, val=0, left: "TreeNode" = None, right: "TreeNode" = None):        self.val = val        self.left = left        self.right = rightclass Solution:    def _find_duplicate_subtrees(self, root: TreeNode,                                 memorandum: Dict[str, int],                                 results: List[TreeNode]) -> Optional[List[int]]:        if not isinstance(root, TreeNode):            return        left = self._find_duplicate_subtrees(root.left, memorandum, results)        right = self._find_duplicate_subtrees(root.right, memorandum, results)        postorder = []        if left:            postorder = postorder + left        else:            postorder.append(left)        if right:            postorder = postorder + right        else:            postorder.append(right)        postorder.append(root.val)        dumped = dumps(postorder)        # if dumped in memorandum.keys() and memorandum[dumped] == 1:        if memorandum.get(dumped, 0) == 1:  # The above commented if-clause is a pedantic counterpart.            results.append(root)        memorandum[dumped] = memorandum.get(dumped, 0) + 1        return postorder    def find_duplicate_subtrees(self, root: Optional[TreeNode]) -> Optional[List[TreeNode]]:        if not isinstance(root, TreeNode):            return        memorandum = dict()        results = []        self._find_duplicate_subtrees(root, memorandum, results)        print("memorandum =", memorandum)        return resultsdef postorder(root: TreeNode, tree: List[Union[int, None]]):    if not root:        tree.append(None)        return    postorder(root.left, tree)    postorder(root.right, tree)    tree.append(root.val)def main():    node7 = TreeNode(4)    node6 = TreeNode(4)    node5 = TreeNode(2, left=node7)    node4 = TreeNode(4)    node3 = TreeNode(3, node5, node6)    node2 = TreeNode(2, left=node4)    node1 = TreeNode(1, node2, node3)    root = node1    sln = Solution()    for root in sln.find_duplicate_subtrees(root):        tree = []        postorder(root, tree)        print("postorder =", dumps(tree))if __name__ == "__main__":    main()

运行上述解答的输出结果为：

memorandum = {"[null, null, 4]": 3, "[null, null, 4, null, 2]": 2, "[null, null, 4, null, 2, null, null, 4, 3]": 1, "[null, null, 4, null, 2, null, null, 4, null, 2, null, null, 4, 3, 1]": 1}postorder = [null, null, 4]postorder = [null, null, 4, null, 2]

实际上， LeetCode 官方通过使用 collections 模块中的 Counter 类，给出了一个如下的非常优雅的解答，其中关于 Counter 类的使用，可以参考【源码共读】Python 标准模块 collections 中 Counter 类详解。

from typing import Optional, List, Dict, Unionfrom collections import Counterclass TreeNode:    def __init__(self, val=0, left: "TreeNode" = None, right: "TreeNode" = None):        self.val = val        self.left = left        self.right = rightclass Solution:    def _collect(self, node: TreeNode, duplicates: List[TreeNode], count: Counter):        if not node:            return "#"        serial = "{},{},{}".format(self._collect(node.left, duplicates, count),                                   self._collect(node.right, duplicates, count),                                   node.val)        count[serial] += 1        if count[serial] == 2:            duplicates.append(node)        return serial    def elegantly_find_duplicate_subtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:        count = Counter()        duplicates = []        self._collect(root, duplicates, count)        return duplicatesdef postorder(root: TreeNode, tree: List[Union[int, None]]):    if not root:        tree.append(None)        return    postorder(root.left, tree)    postorder(root.right, tree)    tree.append(root.val)def main():    node7 = TreeNode(4)    node6 = TreeNode(4)    node5 = TreeNode(2, left=node7)    node4 = TreeNode(4)    node3 = TreeNode(3, node5, node6)    node2 = TreeNode(2, left=node4)    node1 = TreeNode(1, node2, node3)    root = node1    sln = Solution()    for root in sln.elegantly_find_duplicate_subtrees(root):        tree = []        postorder(root, tree)        print("postorder =", dumps(tree))if __name__ == "__main__":    main()

实际上，在上述解答的 第 $15$ 行中，如果将 return "#" 改为 return 也是正确的，但不为何此时在 LeetCode 上提交时，执行耗时和内存消耗的数据都非常差，希望看到这篇题解而且知道缘由的有缘人可以在评论区留下你的指导。

2.3 复杂度

• 时间复杂度： $O(N^2)$ ，当给定二叉树的所有节点呈一条链状时，比较容易分析其最坏时间复杂度： $1+2+\cdots +N$；
• 空间复杂度： $O(N^2)$ ，当给定二叉树的所有节点呈一条链状时，比较容易分析其最坏空间复杂度： $1+2+\cdots +N$。