題目描述：
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.
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
Example 2:
Input: root = [2,1,1]
Output: [[1]]
Example 3:
Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]
Constraints:
The number of the nodes in the tree will be in the range
[1, 10^4]-200 <= Node.val <= 200
一刷題解（DFS + Dictionary）
這題需要我們找到二叉樹中結構相同的子樹並將其中一個子樹的根節點返回出來。如果要知道不同子樹之間的結構，我們需要做兩件事。一是將二叉樹序列化（Serialize），將其變成一個可讀的，可以被識別的字符串或者是HashCode；二是創建一個字典，以序列化後的子樹結構字符串/HashCode為鍵，以該結構的出現次數為值。當我們發現字典裡同樣結構（Key）出現的次數（Value）等於1，也就代表該結構曾經出現過了一次。
二叉樹的序列化其實只是將整個二叉樹中的所有節點（包括空節點）都輸出成一個字符串（節點與節點之間用分隔符分隔），我這裡使用的是比較簡單的前序遍歷/深度優先進行序列化。比如像例子1中的二叉樹，它在序列化後的結果是這樣的：
{ 1, 2, 4, #, #, #, 3, 2, 4, #, #, #, 4, #, # }
當中，’,’為節點間的分隔符，’#’為空節點。這樣看序列化的結果可能不太直觀，但只要我們將每一個遍歷組成的字符串部分拆出來，就能明顯發現重複的部分。比如每個「4」節點的序列化字符串為{ 4, #, # }；每個「2」節點的序列化字符串包含了自己、「4」節點和右邊的空節點，因此它的序列化字符串是{ 2, 4, #, #, # }。我們在遍歷的時候，就可以將這些節點的序列化字符串作為鍵加到字典裡面，然後當遍歷到有同樣的序列化字符串加到字典裡時，就代表這個子樹是「重複」的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
List<TreeNode> res = new List<TreeNode>();
Dictionary<int, int> treeCntDict = new Dictionary<int, int>();
FindDuplicates(res, root, treeCntDict);
return res;
}
string FindDuplicates(List<TreeNode> lis, TreeNode node, Dictionary<int, int> treeCntDict)
{
//遞歸終止點
if(node == null){return string.Empty;}
//前序遍歷序列化，組合自身、左子樹和右子樹的結果成為一個新的序列化字符串
string code = $"{node.val}, " +
$"{FindDuplicates(lis, node.left, treeCntDict)}, " +
$"{FindDuplicates(lis, node.right, treeCntDict)}";
//使用int進行比較比使用string進行比較會更有效率
int codeHash = code.GetHashCode();
//如果字典裡存在該序列化結構並且只有一個，代表本次是該結構的第二次出現，把根節點加到結果列表中
//第二次以上的出現不加到結果列表中
if(treeCntDict.ContainsKey(codeHash) && treeCntDict[codeHash] == 1)
{
lis.Add(node);
}
//第二次以上的出現
if(treeCntDict.ContainsKey(codeHash))
{
treeCntDict[codeHash]++;
}
//每個結構序列化字符串的首次出現都要加到字典裡
else
{
treeCntDict.Add(codeHash, 1);
}
return code;
}
}