LeetCode_二叉树_中等_652.寻找重复的子树
2023-09-27 14:25:46 时间
1.题目
给定一棵二叉树 root,返回所有重复的子树。
对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值,则它们是重复的。
示例 1:
输入:root = [1,2,3,4,null,2,4,null,null,4]
输出:[[2,4],[4]]
示例 2:
输入:root = [2,1,1]
输出:[[1]]
示例 3:
输入:root = [2,2,2,3,null,3,null]
输出:[[2,3],[3]]
提示:
树中的结点数在[1,104]范围内。
-200 <= Node.val <= 200
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-duplicate-subtrees
2.思路
(1)递归
3.代码实现(Java)
//思路1————递归
/**
* 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 {
/*
map 记录所有子树出现的次数
键: 子树按照后序遍历组成的节点值序列,中间用","隔开,最终形成一个字符串
值: 该字符串在 map 中出现的次数
*/
HashMap<String, Integer> map = new HashMap<>();
// res 用于保存最终结果
ArrayList<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
public String traverse(TreeNode root) {
if (root == null) {
return "";
}
String left = traverse(root.left);
String right = traverse(root.right);
//按照后序遍历组成的节点值序列,中间用","隔开
String subTree = left + "," + right + "," + root.val;
//从 map 中查询当前子树 subTree 出现的次数,如果 map 中没有,则返回 0
int cnt = map.getOrDefault(subTree, 0);
// cnt == 1 说明 map 中已经存在当前子树,故将其加入到 res 中
if (cnt == 1) {
res.add(root);
}
// map 中对应子树出现的次数 + 1
map.put(subTree, cnt + 1);
return subTree;
}
}
相关文章
- 【LeetCode】二叉树展开为链表 [M](Morris遍历)
- 【LeetCode】二叉搜索树中第K小的元素 [M](二叉树遍历)
- leetcode 226 Invert Binary Tree 翻转二叉树
- LeetCode_位运算_中等_318.最大单词长度乘积
- LeetCode_排序_双指针_中等_524.通过删除字母匹配到字典里最长单词
- LeetCode_二分搜索_中等_540.有序数组中的单一元素
- LeetCode_二叉树_中等_623.在二叉树中增加一行
- LeetCode_二叉树_困难_124. 二叉树中的最大路径和
- LeetCode_二叉树_简单_94.二叉树的中序遍历
- LeetCode_回溯算法_动态规划_简单_104.二叉树的最大深度
- LeetCode_排序_中等_179.最大数
- LeetCode·每日一题·816.模糊坐标·模拟
- leetcode day6 -- String to Integer (atoi) && Best Time to Buy and Sell Stock I II III
- 【LeetCode从零单排】No104 Maximum Depth of Binary Tree
- 【LeetCode从零单排】No19.RemoveNthNodeFromEndofList
- LeetCode-145. 二叉树的后序遍历(java)
- [LeetCode] 655. Print Binary Tree 打印二叉树
- [LeetCode] 654. Maximum Binary Tree 最大二叉树
- [LeetCode] 35. Search Insert Position 搜索插入位置
- [LeetCode] 257. Binary Tree Paths 二叉树路径
- [LeetCode] 621. Task Scheduler 任务调度
- [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度
- leetcode 1382 将二叉搜索树变平衡
- leetcode 105 从前序与中序遍历序列构造二叉树
- leetcode 124 二叉树的最大路径和
- leetcode 700 二叉树中的搜索树
- leetcode 459 重复的子字符串