原题
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例1:
1 / \ 2 3 / / \ 4 2 4 / 4
下面是两个重复的子树：
2 / 4
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。
解法
思想
将子树按照某种算法遍历序列化成字符串，作为哈希表的键。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<String,Integer> map;
List<TreeNode> list;
public String LRD(TreeNode node){
StringBuilder sb = new StringBuilder();
dfs(sb,node);
return sb.toString();
}
public void dfs(StringBuilder str,TreeNode node){
if(node == null){
str.append('n');
return;
}
dfs(str,node.left);
dfs(str,node.right);
str.append(String.valueOf(node.val));
return;
}
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
map = new HashMap<>();
list = new ArrayList<>();
dfsFindSubtrees(root);
return list;
}
public void dfsFindSubtrees(TreeNode root){
if(root == null) return;
dfsFindSubtrees(root.left);
dfsFindSubtrees(root.right);
String LRD = LRD(root);
if(map.containsKey(LRD)){
if(map.get(LRD)==1){
list.add(root);
map.put(LRD,0);
}
}else{
map.put(LRD,1);
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode652-%e5%af%bb%e6%89%be%e9%87%8d%e5%a4%8d%e7%9a%84%e5%ad%90%e6%a0%91/
相关推荐
-
leetcode374-猜数字大小
原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...
-
leetcode11-盛最多水的容器
原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...
-
leetcode219-存在重复元素II
原题 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。 示例1...
-
leetcode4-寻找两个有序数组的中位数
这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m...
-
leetcode983-最低票价
原题 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车...
-
leetcode134-加油站
原题 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[...
-
leetcode217-存在重复元素
原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...
-
leetcode599-两个列表的最小索引总和
原题 假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果...
-
leetcode402-移掉K位数字
原题 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意： num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 ...
