2018-07-29 17:42:29

問(wèn)題描述：

問(wèn)題求解：

本題是要求尋找一棵樹(shù)中的重復(fù)子樹(shù)，問(wèn)題的難點(diǎn)在于如何在遍歷的時(shí)候?qū)χ氨闅v過(guò)的子樹(shù)進(jìn)行描述和保存。

這里就需要使用之前使用過(guò)的二叉樹(shù)序列化的手法，將遍歷到的二叉樹(shù)進(jìn)行序列化表達(dá)，我們知道序列化的二叉樹(shù)可以唯一的表示一棵二叉樹(shù)，并可以用來(lái)反序列化。

想到這里其實(shí)問(wèn)題就已經(jīng)解決了一大半了， 我們只需要在遍歷的過(guò)程中將每次的序列化結(jié)果保存到一個(gè)HashMap中，并對(duì)其進(jìn)行計(jì)數(shù)，如果重復(fù)出現(xiàn)了，那么將當(dāng)前的節(jié)點(diǎn)添加到res中即可。

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {List<TreeNode> res = new ArrayList<>();Map<String, Integer> map = new HashMap<>();helper(root, map, res);return res;}private String helper(TreeNode root, Map<String, Integer> map, List<TreeNode> res) {if (root == null) return "#";String str = root.val + "," + helper(root.left, map, res) + "," + helper(root.right, map, res);if (map.containsKey(str)) {if (map.get(str) == 1) res.add(root);map.put(str, map.get(str) + 1);}else map.put(str, 1);return str;}

算法改進(jìn)：

上述的算法基本可以在O(n)的時(shí)間復(fù)雜度解決問(wèn)題，但是其中的字符串拼接是非常耗時(shí)的，這里可以對(duì)這個(gè)部分做出一點(diǎn)改進(jìn)。如果我們不用序列化結(jié)果來(lái)表征一個(gè)子樹(shù)，用一個(gè)id值來(lái)表征的話(huà)，那么就可以規(guī)避掉字符串拼接的問(wèn)題。

這里直接使用id的size來(lái)進(jìn)行id的分配，值得注意的是由于已經(jīng)給null分配了0，那么每次分配的大小應(yīng)該是size + 1。

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {List<TreeNode> res = new ArrayList<>();Map<Long, Integer> id = new HashMap<>();Map<Integer, Integer> map = new HashMap<>();helper(root, id, map, res);return res;}private Integer helper(TreeNode root, Map<Long, Integer> id, Map<Integer, Integer> map, List<TreeNode> res) {if (root == null) return 0;Long key = ((long) root.val << 32) | helper(root.left, id, map, res) << 16 | helper(root.right, id, map, res);if (!id.containsKey(key)) id.put(key, id.size() + 1);int curId = id.get(key);if (map.containsKey(curId)) {if (map.get(curId) == 1) res.add(root);map.put(curId, map.get(curId) + 1);}else map.put(curId, 1);return curId;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/TIMHY/p/9386093.html

總結(jié)

以上是生活随笔為你收集整理的寻找重复的子树 Find Duplicate Subtrees的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。