Problem: 652. 尋找重復的子樹

題目描述

思路

1.利用二叉樹的后序遍歷將原始的二叉樹序列化（之所以利用后序遍歷是因為其在歸的過程中是會攜帶左右子樹的節點信息,而這些節點信息正是該解法要利用的東西）；
2.在一個哈希表中存儲每一個序列化后子樹和其出現的次數（初始時設為出現0次，每當有一次重復就將其次數加一）；
3.將哈希表中出現次數大于等于1的子樹的節點添加到一個結果集合中

復雜度

時間復雜度:

$O(n)$；其中$n$二叉樹中節點的個數

空間復雜度:

$O(n)$

Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// Record all subtrees and the number of occurrencesMap<String, Integer> memo = new HashMap<>();// Record duplicate child root nodesList<TreeNode> res = new LinkedList<>();/*** Find Duplicate Subtrees** @param root The root of binary tree* @return List<TreeNode>*/public List<TreeNode> findDuplicateSubtrees(TreeNode root) {traverse(root);return res;}/*** Find Duplicate Subtrees(Implementation function)** @param root The root of binary tree* @return String*/private String traverse(TreeNode root) {if (root == null) {return "#";}String left = traverse(root.left);String right = traverse(root.right);String subTree = left + "," + right + "," + root.val;int freq = memo.getOrDefault(subTree, 0);// Multiple repetitions will only be added to the result set onceif (freq == 1) {res.add(root);}// Add one to the number of// occurrences corresponding to the subtreememo.put(subTree, freq + 1);return subTree;}
}