{"id":699,"date":"2021-02-16T16:05:26","date_gmt":"2021-02-16T08:05:26","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=699"},"modified":"2021-02-17T14:38:29","modified_gmt":"2021-02-17T06:38:29","slug":"leetcode-652","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/02\/16\/leetcode-652\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 652 – Find Duplicate Subtrees"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

Given the <\/span>root<\/code><\/span> of a binary tree, return all <\/span>duplicate subtrees<\/span><\/strong><\/span>.<\/span><\/p>

For each kind of duplicate subtrees, you only need to return the root node of any <\/span>one<\/span><\/strong><\/span> of them.<\/span><\/p>

Two trees are <\/span>duplicate<\/span><\/strong><\/span> if they have the <\/span>same structure<\/span><\/strong><\/span> with the <\/span>same node values<\/span><\/strong><\/span>.<\/span><\/p>

\u00a0<\/p>

Example 1:<\/span><\/strong><\/span><\/p>

\"img\"<\/span><\/p>

Input: root = [1,2,3,4,null,2,4,null,null,4]<\/span>
Output: [[2,4],[4]]<\/span><\/pre>
Example 2:<\/span><\/strong><\/span><\/p>
\"img\"<\/span><\/p>
Input: root = [2,1,1]<\/span>
Output: [[1]]<\/span><\/pre>
Example 3:<\/span><\/strong><\/span><\/p>
\"img\"<\/span><\/p>
Input: root = [2,2,2,3,null,3,null]<\/span>
Output: [[2,3],[3]]<\/span><\/pre>
\u00a0<\/p>
Constraints:<\/span><\/strong><\/span><\/p>
  • The number of the nodes in the tree will be in the range <\/span>[1, 10^4]<\/code><\/span><\/p><\/li>
  • -200 <= Node.val <= 200<\/code><\/span><\/p><\/li><\/ul>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    \u4e00\u5237\u984c\u89e3\uff08DFS + Dictionary\uff09<\/strong><\/span><\/h4>
    \u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u9700\u8981\u6211\u5011\u627e\u5230\u4e8c\u53c9\u6a39\u4e2d\u7d50\u69cb\u76f8\u540c\u7684\u5b50\u6a39\u4e26\u5c07\u5176\u4e2d\u4e00\u500b\u5b50\u6a39\u7684\u6839\u7bc0\u9ede\u8fd4\u56de\u51fa\u4f86\u3002\u5982\u679c\u8981\u77e5\u9053\u4e0d\u540c\u5b50\u6a39\u4e4b\u9593\u7684\u7d50\u69cb\uff0c\u6211\u5011\u9700\u8981\u505a\u5169\u4ef6\u4e8b\u3002\u4e00\u662f\u5c07\u4e8c\u53c9\u6a39\u5e8f\u5217\u5316\uff08Serialize\uff09\uff0c\u5c07\u5176\u8b8a\u6210\u4e00\u500b\u53ef\u8b80\u7684\uff0c\u53ef\u4ee5\u88ab\u8b58\u5225\u7684\u5b57\u7b26\u4e32\u6216\u8005\u662fHashCode\uff1b\u4e8c\u662f\u5275\u5efa\u4e00\u500b\u5b57\u5178\uff0c\u4ee5\u5e8f\u5217\u5316\u5f8c\u7684\u5b50\u6a39\u7d50\u69cb\u5b57\u7b26\u4e32\/HashCode\u70ba\u9375\uff0c\u4ee5\u8a72\u7d50\u69cb\u7684\u51fa\u73fe\u6b21\u6578\u70ba\u503c\u3002<\/span>\u7576\u6211\u5011\u767c\u73fe\u5b57\u5178\u88e1\u540c\u6a23\u7d50\u69cb\uff08Key\uff09\u51fa\u73fe\u7684\u6b21\u6578\uff08Value\uff09\u7b49\u65bc1\uff0c\u4e5f\u5c31\u4ee3\u8868\u8a72\u7d50\u69cb\u66fe\u7d93\u51fa\u73fe\u904e\u4e86\u4e00\u6b21\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u4e8c\u53c9\u6a39\u7684\u5e8f\u5217\u5316\u5176\u5be6\u53ea\u662f\u5c07\u6574\u500b\u4e8c\u53c9\u6a39\u4e2d\u7684\u6240\u6709\u7bc0\u9ede\uff08\u5305\u62ec\u7a7a\u7bc0\u9ede\uff09\u90fd\u8f38\u51fa\u6210\u4e00\u500b\u5b57\u7b26\u4e32\uff08\u7bc0\u9ede\u8207\u7bc0\u9ede\u4e4b\u9593\u7528\u5206\u9694\u7b26\u5206\u9694\uff09\uff0c\u6211\u9019\u88e1\u4f7f\u7528\u7684\u662f\u6bd4\u8f03\u7c21\u55ae\u7684\u524d\u5e8f\u904d\u6b77\/\u6df1\u5ea6\u512a\u5148\u9032\u884c\u5e8f\u5217\u5316\u3002\u6bd4\u5982\u50cf\u4f8b\u5b501\u4e2d\u7684\u4e8c\u53c9\u6a39\uff0c\u5b83\u5728\u5e8f\u5217\u5316\u5f8c\u7684\u7d50\u679c\u662f\u9019\u6a23\u7684\uff1a<\/p>
    { 1, 2, 4, #, #, #, 3, 2, 4, #, #, #,\u00a0 4, #, # }<\/span><\/strong><\/h5>
    \"img\"<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u7576\u4e2d\uff0c’,’\u70ba\u7bc0\u9ede\u9593\u7684\u5206\u9694\u7b26\uff0c’#’\u70ba\u7a7a\u7bc0\u9ede\u3002\u9019\u6a23\u770b\u5e8f\u5217\u5316\u7684\u7d50\u679c\u53ef\u80fd\u4e0d\u592a\u76f4\u89c0\uff0c\u4f46\u53ea\u8981\u6211\u5011\u5c07\u6bcf\u4e00\u500b\u904d\u6b77\u7d44\u6210\u7684\u5b57\u7b26\u4e32\u90e8\u5206\u62c6\u51fa\u4f86\uff0c\u5c31\u80fd\u660e\u986f\u767c\u73fe\u91cd\u8907\u7684\u90e8\u5206\u3002\u6bd4\u5982\u6bcf\u500b\u300c4\u300d\u7bc0\u9ede\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u70ba{ 4, #, # }<\/span>\uff1b\u6bcf\u500b\u300c2\u300d\u7bc0\u9ede\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u5305\u542b\u4e86\u81ea\u5df1\u3001\u300c4\u300d\u7bc0\u9ede\u548c\u53f3\u908a\u7684\u7a7a\u7bc0\u9ede\uff0c\u56e0\u6b64\u5b83\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u662f{ 2, 4, #, #, # }<\/span>\u3002\u6211\u5011\u5728\u904d\u6b77\u7684\u6642\u5019\uff0c\u5c31\u53ef\u4ee5\u5c07\u9019\u4e9b\u7bc0\u9ede\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u4f5c\u70ba\u9375\u52a0\u5230\u5b57\u5178\u88e1\u9762\uff0c\u7136\u5f8c\u7576\u904d\u6b77\u5230\u6709\u540c\u6a23\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u52a0\u5230\u5b57\u5178\u88e1\u6642\uff0c\u5c31\u4ee3\u8868\u9019\u500b\u5b50\u6a39\u662f\u300c\u91cd\u8907\u300d\u7684\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    \/**<\/span><\/span>
     * Definition for a binary tree node.<\/span><\/span>
     * public class TreeNode {<\/span><\/span>
     * \u00a0 \u00a0 public int val;<\/span><\/span>
     * \u00a0 \u00a0 public TreeNode left;<\/span><\/span>
     * \u00a0 \u00a0 public TreeNode right;<\/span><\/span>
     * \u00a0 \u00a0 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {<\/span><\/span>
     * \u00a0 \u00a0 \u00a0 \u00a0 this.val = val;<\/span><\/span>
     * \u00a0 \u00a0 \u00a0 \u00a0 this.left = left;<\/span><\/span>
     * \u00a0 \u00a0 \u00a0 \u00a0 this.right = right;<\/span><\/span>
     * \u00a0 \u00a0 }<\/span><\/span>
     * }<\/span><\/span>
     *\/<\/span><\/span>
    public<\/span> class<\/span> Solution<\/span> {<\/span>
     \u00a0 \u00a0public<\/span> IList<\/span><<\/span>TreeNode<\/span>><\/span> FindDuplicateSubtrees<\/span>(TreeNode<\/span> root<\/span>) {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0List<\/span><<\/span>TreeNode<\/span>><\/span> res<\/span> =<\/span> new<\/span> List<\/span><<\/span>TreeNode<\/span>><\/span>();<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span> treeCntDict<\/span> =<\/span> new<\/span> Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span>();<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0FindDuplicates<\/span>(res<\/span>, root<\/span>, treeCntDict<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> res<\/span>;<\/span>
     \u00a0  }<\/span>
     \u00a0 \u00a0string<\/span> FindDuplicates<\/span>(List<\/span><<\/span>TreeNode<\/span>><\/span> lis<\/span>, TreeNode<\/span> node<\/span>, Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span> treeCntDict<\/span>)<\/span>
     \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u905e\u6b78\u7d42\u6b62\u9ede<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(node<\/span> ==<\/span> null<\/span>){return<\/span> string<\/span>.Empty<\/span>;}<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u524d\u5e8f\u904d\u6b77\u5e8f\u5217\u5316\uff0c\u7d44\u5408\u81ea\u8eab\u3001\u5de6\u5b50\u6a39\u548c\u53f3\u5b50\u6a39\u7684\u7d50\u679c\u6210\u70ba\u4e00\u500b\u65b0\u7684\u5e8f\u5217\u5316\u5b57\u7b26\u4e32<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0string<\/span> code<\/span> =<\/span> $<\/span>\"{node.val}, \"<\/span> +<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0$<\/span>\"{FindDuplicates(lis, node.left, treeCntDict)}, \"<\/span> +<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0$<\/span>\"{FindDuplicates(lis, node.right, treeCntDict)}\"<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u4f7f\u7528int\u9032\u884c\u6bd4\u8f03\u6bd4\u4f7f\u7528string\u9032\u884c\u6bd4\u8f03\u6703\u66f4\u6709\u6548\u7387<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0int<\/span> codeHash<\/span> =<\/span> code<\/span>.GetHashCode<\/span>();<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u5982\u679c\u5b57\u5178\u88e1\u5b58\u5728\u8a72\u5e8f\u5217\u5316\u7d50\u69cb\u4e26\u4e14\u53ea\u6709\u4e00\u500b\uff0c\u4ee3\u8868\u672c\u6b21\u662f\u8a72\u7d50\u69cb\u7684\u7b2c\u4e8c\u6b21\u51fa\u73fe\uff0c\u628a\u6839\u7bc0\u9ede\u52a0\u5230\u7d50\u679c\u5217\u8868\u4e2d<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u7b2c\u4e8c\u6b21\u4ee5\u4e0a\u7684\u51fa\u73fe\u4e0d\u52a0\u5230\u7d50\u679c\u5217\u8868\u4e2d<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(treeCntDict<\/span>.ContainsKey<\/span>(codeHash<\/span>) &&<\/span> treeCntDict<\/span>[codeHash<\/span>] ==<\/span> 1<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0lis<\/span>.Add<\/span>(node<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u7b2c\u4e8c\u6b21\u4ee5\u4e0a\u7684\u51fa\u73fe<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(treeCntDict<\/span>.ContainsKey<\/span>(codeHash<\/span>))<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0treeCntDict<\/span>[codeHash<\/span>]++<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/\u6bcf\u500b\u7d50\u69cb\u5e8f\u5217\u5316\u5b57\u7b26\u4e32\u7684\u9996\u6b21\u51fa\u73fe\u90fd\u8981\u52a0\u5230\u5b57\u5178\u88e1<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0else<\/span><\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0treeCntDict<\/span>.Add<\/span>(codeHash<\/span>, 1<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> code<\/span>;<\/span>
     \u00a0  }<\/span>
    }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
    \u984c\u76ee\u63cf\u8ff0\uff1a Given the root of a binary tree, return all dupli …<\/p>\n
      [LeetCode\u5237\u984c\u7b46\u8a18] 652 – Find Duplicate Subtrees<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-699","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/699","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=699"}],"version-history":[{"count":14,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/699\/revisions"}],"predecessor-version":[{"id":714,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/699\/revisions\/714"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=699"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=699"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=699"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}