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

野性酷女 2022-11-03 00:43 86阅读 0赞

## 问题 ##

[力扣][Link 1]

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

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

**示例 1：**

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

下面是两个重复的子树：

2
     /
    4

和

4

因此，你需要以列表的形式返回上述重复子树的根结点。

## 思路 ##

**后序遍历**

## 代码 ##

### Python3 ###

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, val=0, left=None, right=None):
    # self.val = val
    # self.left = left
    # self.right = right
    class Solution:
        def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
            import collections
            res = []
            counter = collections.Counter()
    
            def traverse(root):
                if not root:
                    return '#'
                # 后序遍历
                left = traverse(root.left)
                right = traverse(root.right)
                chain = left + ',' + right + ',' + str(root.val)
                counter[chain] += 1
                # 统计出现两次即是重复子树，加入res
                if counter[chain] == 2:
                    res.append(root)
                return chain
            
            traverse(root)
            return res

## 链接 ##

[GitHub][]

[Link 1]: https://leetcode-cn.com/problems/find-duplicate-subtrees/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/0652-Find-Duplicate-Subtrees

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode python 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

末蓝、/ 2024年02月18日 14:45/ 0 赞/ 18 阅读

相关 leetcode 寻找重复的子树

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

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

相关 Java实现 LeetCode 652 寻找重复的子树（两个map的DFS）

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

桃扇骨/ 2023年07月21日 05:57/ 0 赞/ 7 阅读

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

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

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

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

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

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

相关 LeetCode 287. 寻找重复数

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

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

相关 Leetcode 287. 寻找重复数

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

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

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

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

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

相关 python—leetcode-459. 重复的子字符串

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

谁借莪１个温暖的怀抱￠/ 2022年05月20日 00:59/ 0 赞/ 198 阅读

相关 LeetCode287——寻找重复数

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

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