原题
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例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/
相关推荐
-
leetcode155-最小栈
原题 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() ...
-
leetcode11-盛最多水的容器
原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...
-
剑指offer51-数组中的逆序对
原题（来源Leetcode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入： [7...
-
leetcode380-常数时间插入、删除和获取随机元素
原题 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。 insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 v...
-
leetcode47-全排列II
原题 给定一个可包含重复数字的序列，返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题...
-
leetcode27-移除元素
原题 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(...
-
leetcode153-寻找旋转排序数组中的最小值
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...
-
leetcode32-最长有效括号
原题 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2...
-
leetcode410-分割数组的最大值
原题 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1...
-
leetcode26-删除排序数组中的重复项
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空...
