infrastructureDataStructure4

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/find-duplicate-subtrees/]

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

1
2
3
4
5
6
7
    1
   / \
  2   3
 /   / \
4   2   4
   /
  4

下面是两个重复的子树：

1
2
3
  2
 /
4

和

1
4

因此，你需要以列表的形式返回上述重复子树的根结点。

算法描述

  1. 使用 unordered_map 记录每个子树经过哈希后的数量，哈希方法可以用最简单的前序遍历，即 根节点,左子树,右子树 的方式递归构造。每个叶子结点下的空结点的位置需要保留。
  2. 若发现当前子树在哈希表第二次出现，则将该结点记入答案列表。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        vector<TreeNode*> ans;
        unordered_map<string,int> mp;
        if(root==NULL)return ans;
        dfs(root,ans,mp);
        return ans;
    }
    
    string dfs(TreeNode* root,vector<TreeNode*> &ans,unordered_map<string,int> &mp){
        if(root==NULL)return "#";
        string left = dfs(root->left,ans,mp);
        string right = dfs(root->right,ans,mp);
        string str = to_string(root->val)+left+right;
        if(mp[str]==1)ans.push_back(root);
        mp[str]++;
        return str;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<TreeNode> ans = new ArrayList<TreeNode>();
    HashMap<String,Integer> hm = new HashMap<String,Integer>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if(root==null)return ans;
        dfs(root);
        return ans;
    }

    public String dfs(TreeNode root){
        if(root==null)return "#";
        String left = dfs(root.left);
        String right = dfs(root.right);
        String str = new String();
        str = root.val+left+right;
        if(hm.containsKey(str)&&hm.get(str)==1)ans.add(root);
        hm.put(str,hm.getOrDefault(str,0)+1);//如果不包含该键值，返回0，否则返回当前值
        return str;
    }
}