leetcode 寻找重复的子树

不念不忘少年蓝@ 2023-08-17 15:43 76阅读 0赞

> 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

> 两棵树重复是指它们具有相同的结构以及相同的结点值。

> 示例 1：

1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

> 下面是两个重复的子树：

2
     /
    4

> 和

4

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/find-duplicate-subtrees][https_leetcode-cn.com_problems_find-duplicate-subtrees]  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法一：暴力枚举  
算法二：哈希表优化第二维，每次将之前遍历过的存下来，使用前序遍历变为序列化

class Solution {
    public:
        vector<TreeNode*> res;
        unordered_map<string,int> h;
        string dfs(TreeNode* root)
        {
            if(!root)return "#";
            string cur="";
            cur+=to_string(root->val)+','+dfs(root->left)+','+dfs(root->right);
            h[cur]++;
            if(h[cur]==2){
                res.push_back(root);
            }
            return cur;
        }
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
            dfs(root);
            return res;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11417696.html

[https_leetcode-cn.com_problems_find-duplicate-subtrees]: https://leetcode-cn.com/problems/find-duplicate-subtrees

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 寻找重复的子树

> 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 > 两棵树重复是指它们具有相同的结构以及相同的结点值。 > 示例 1：

不念不忘少年蓝@/ 2023年08月17日 15:43/ 0 赞/ 77 阅读

相关 652. 寻找重复的子树(将string用id唯一标识)

\\\ 解题思路把每个子树用(根,左节点,右节点)这样的形式用一个id唯一标识然后再开一个哈希表统计这个id出现的次数 \\\ 代码 class Solut

水深无声/ 2023年01月06日 15:59/ 0 赞/ 59 阅读

相关（js）leetcode 652. 寻找重复的子树

题目： > 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 > > 两棵树重复是指它们具有相同的结构以及相同的结点值。

雨点打透心脏的1/2处/ 2022年11月06日 08:56/ 0 赞/ 119 阅读

相关 LeetCode | 0652. 寻找重复的子树【Python】

问题 [力扣][Link 1] 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及

野性酷女/ 2022年11月03日 00:43/ 0 赞/ 62 阅读

相关 LeetCode 287. 寻找重复数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年10月26日 04:00/ 0 赞/ 128 阅读

相关 Leetcode 287. 寻找重复数

题目重述给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个

港控/mmm°/ 2022年09月15日 14:59/ 0 赞/ 135 阅读

相关 652 寻找重复的子树（树的哈希）

1. 问题描述：给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。示例

朱雀/ 2022年08月29日 09:39/ 0 赞/ 75 阅读

相关 leetcode 459. Repeated Substring Pattern 重复子串的确定 + 不需要寻找重复出现的子串 + 暴力拼接即可

Given a non-empty string check if it can be constructed by taking a substring of it and

向右看齐/ 2022年05月31日 01:39/ 0 赞/ 134 阅读

相关 LeetCode——重复的子字符串

题目：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。示例 1: 输入: "abab

秒速五厘米/ 2022年03月17日 12:34/ 0 赞/ 218 阅读

相关 LeetCode287——寻找重复数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

本是古典何须时尚/ 2022年01月25日 22:13/ 0 赞/ 215 阅读