問(wèn)題
給定一棵二叉樹婚被，返回所有重復(fù)的子樹狡忙。對(duì)于同一類的重復(fù)子樹，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可址芯。
兩棵樹重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值灾茁。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是兩個(gè)重復(fù)的子樹：
2
/
4
和
4
因此窜觉，你需要以列表的形式返回上述重復(fù)子樹的根結(jié)點(diǎn)。
思路
后序遍歷
代碼
Python3
# 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]:
import collections
res = []
counter = collections.Counter()
def traverse(root):
if not root:
return '#'
# 后序遍歷
left = traverse(root.left)
right = traverse(root.right)
chain = left + ',' + right + ',' + str(root.val)
counter[chain] += 1
# 統(tǒng)計(jì)出現(xiàn)兩次即是重復(fù)子樹北专，加入res
if counter[chain] == 2:
res.append(root)
return chain
traverse(root)
return res
