###### tags: `Leetcode` `medium` `tree` `hash` `python` `c++`

# 652. Find Duplicate Subtrees

## [題目連結:] https://leetcode.com/problems/find-duplicate-subtrees/

## 題目:
Given the ```root``` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.


## 解題想法:
* 此題為，找出二元樹中所有的重複子樹

* 使用字典紀錄:
* dictionary:
* key: path
* value: 出現次數
* 對於每顆子樹，將其結構依照**preorder traversal**遍歷保存，存於hash table中
* ex: 若重複為tree:245
* 則res=[[2],[4],[5]]
* 因為可以形成分別245、45、5三個tree
* 使用preorder，才可以保證單一子樹5可以記錄到
* 當下次再次出現此結構，即可將該root加入到最終結果

## Python:

from collections import defaultdict

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        self.res=[]
        dic=defaultdict(int) #key為path value為出現次數
        self.traversal(root,dic)
        print(dic)
        return self.res
    def traversal(self,root,dic):
        if not root:
            return '#'
        #preorder
        path= str(root.val)+','+self.traversal(root.left,dic)+','+self.traversal(root.right,dic)
        if dic[path]==1: #該path出現過ㄌ
            self.res.append(root)
        dic[path]+=1
        return path

root=TreeNode(1)
root.insertLeft(2)
root.insertRight(3)
root.left.insertLeft(4)
root.left.left.insertLeft(5)
root.right.insertLeft(2)
root.right.insertRight(5)
root.right.left.insertLeft(4)
root.right.left.left.insertLeft(5)
root.printTree()

result=Solution()
ans=result.findDuplicateSubtrees(root)
print(ans)
'''
ex:
            1
        2       3
    4         2     5
5           4
          5

res=[[2],[4],[5]]
'''

## C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> dic;
        Traversal(root, dic);
        return res;
    }
    string Traversal(TreeNode* root, unordered_map<string, int>& dic){
        if (!root)
            return "#";
        //to_string: Returns a string with the representation of val.
        string path=to_string(root->val)+","+Traversal(root->left, dic)+","+Traversal(root->right, dic);
        if (dic[path]==1)
            res.push_back(root);
        dic[path]+=1;
        return path;
    }

private:
    vector<TreeNode*> res;
};