Leetcode 652 Solution

This article provides solution to leetcode question 652 (find-duplicate-subtrees)

https://leetcode.com/problems/find-duplicate-subtrees

Solution

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution(object): def dfs(self, root): if root == None: return "#" res = "{},{},{}".format( root.val, self.dfs(root.left), self.dfs(root.right), )
if res not in self.cache: self.cache[res] = root else: if self.cache[res] is not None: self.ans.append(root) self.cache[res] = None return res
def findDuplicateSubtrees(self, root): """ :type root: TreeNode :rtype: List[TreeNode] """ self.cache = {} self.ans = [] self.dfs(root) return self.ans