LeetCode 652. Find Duplicate Subtrees

发布时间：2020-12-14 04:43:47 所属栏目：大数据来源：网络整理

导读：原题链接在这里：https://leetcode.com/problems/find-duplicate-subtrees/ 题目： Given 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 du

原题链接在这里：https://leetcode.com/problems/find-duplicate-subtrees/

题目：

Given 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 same node values.

Example 1:

        1
       /       2   3
     /   /     4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

Therefore,you need to return above trees‘ root in the form of a list.

题解：

Do preorder serialization in subtree and see this serialization happens before.?

Use a HashMap to maintain the frequency of serialization.

Time Complexity: O(n).

Space: O(n).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
12         HashMap<String,Integer> hm = new HashMap<String,Integer>();
13         List<TreeNode> res = new ArrayList<TreeNode>();
14         preorder(root,hm,res);
15         return res;
16     }
17     
18     private String preorder(TreeNode root,HashMap<String,Integer> hm,List<TreeNode> res){
19         if(root == null){
20             return "#";
21         }
22         
23         String key = root.val + "," + preorder(root.left,res) + "," + preorder(root.right,res);
24         if(hm.containsKey(key) && hm.get(key) == 1){
25             res.add(root);
26         }
27         
28         hm.put(key,hm.getOrDefault(key,0)+1);
29         return key;
30     }
31 }

类似Serialize and Deserialize BST,?Serialize and Deserialize Binary Tree.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!