文章目錄

• • 1. 題目
  • • 1.1 示例
    • 1.2 說(shuō)明
    • 1.3 限制
  • 2. 解法一
  • • 2.1 分析
    • 2.2 實(shí)現(xiàn)
    • 2.3 復(fù)雜度

1. 題目

給定一棵二叉樹(shù)的根節(jié)點(diǎn)，請(qǐng)返回所有的重復(fù)子樹(shù)。對(duì)于每一類(lèi)重復(fù)子樹(shù)，你只需要返回其中任意一個(gè)的根節(jié)點(diǎn)即可。如果兩棵二叉樹(shù)擁有相同的結(jié)構(gòu)和節(jié)點(diǎn)值，則稱(chēng)這兩棵二叉樹(shù)是重復(fù)的。

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 說(shuō)明

• 來(lái)源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/find-duplicate-subtrees

1.3 限制

• 二叉樹(shù)中的節(jié)點(diǎn)數(shù)量在 $[1,\text{?}10^4]$ 之間；
• -200 <= Node.val <= 200 。

2. 解法一

2.1 分析

想要正確解答本題，只需要知道如何給出二叉樹(shù)的某種唯一性表達(dá)即可，接下來(lái)首先獲得以給定二叉樹(shù)的所有節(jié)點(diǎn)為根節(jié)點(diǎn)的子二叉樹(shù)的表達(dá)形式，然后得到所有重復(fù)表達(dá)形式對(duì)應(yīng)子樹(shù)的根節(jié)點(diǎn)即可。

實(shí)際上，所謂給出二叉樹(shù)的某種唯一表達(dá)其實(shí)就是對(duì)二叉樹(shù)進(jìn)行序列化，而在【LeetCode 二叉樹(shù)專(zhuān)項(xiàng)】二叉樹(shù)的序列化與反序列化（297）中，我們給出了基于二叉樹(shù)深度優(yōu)先搜索（前序遍歷、后序遍歷）以及廣度優(yōu)先搜索實(shí)現(xiàn)的二叉樹(shù)序列化。

接下來(lái)，需要確定就是具體采用哪種方式序列化。本題采用二叉樹(shù)的后序遍歷對(duì)給定二叉樹(shù)的所有子樹(shù)進(jìn)行序列化。

2.2 實(shí)現(xiàn)

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()

運(yùn)行上述解答的輸出結(jié)果為：

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]

實(shí)際上， LeetCode 官方通過(guò)使用 collections 模塊中的 Counter 類(lèi)，給出了一個(gè)如下的非常優(yōu)雅的解答，其中關(guān)于 Counter 類(lèi)的使用，可以參考【源碼共讀】Python 標(biāo)準(zhǔn)模塊 collections 中 Counter 類(lèi)詳解。

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()

實(shí)際上，在上述解答的 第 $15$ 行中，如果將 return "#" 改為 return 也是正確的，但不為何此時(shí)在 LeetCode 上提交時(shí)，執(zhí)行耗時(shí)和內(nèi)存消耗的數(shù)據(jù)都非常差，希望看到這篇題解而且知道緣由的有緣人可以在評(píng)論區(qū)留下你的指導(dǎo)。

2.3 復(fù)雜度

• 時(shí)間復(fù)雜度： $O(N^2)$ ，當(dāng)給定二叉樹(shù)的所有節(jié)點(diǎn)呈一條鏈狀時(shí)，比較容易分析其最壞時(shí)間復(fù)雜度： $1+2+?+N$；
• 空間復(fù)雜度： $O(N^2)$ ，當(dāng)給定二叉樹(shù)的所有節(jié)點(diǎn)呈一條鏈狀時(shí)，比較容易分析其最壞空間復(fù)雜度： $1+2+?+N$。