导航：首页 > 互联网科技 >

python二叉树怎样寻找重复的子树

发表于：2025-12-01 作者：千家信息网编辑

千家信息网最后更新 2025年12月01日，这篇文章给大家介绍python二叉树怎样寻找重复的子树，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意

千家信息网最后更新 2025年12月01日python二叉树怎样寻找重复的子树

这篇文章给大家介绍python二叉树怎样寻找重复的子树，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

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

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

示例 1：

下面是两个重复的子树：

2
     /
    4

和

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

解题思路：

1，重复子树意思是从根节点到叶子节点一样

2，重复多次只取一个，所以用hash存次数，取次数为2的作为解雇

3，虽然前序＋中序遍历可以恢复二叉树，但是对于元素值相同的不同二叉树，前序，中序遍历结果是一样的，没法区分。

0 和 0

／ \

0 0

4，因此采用leetcode序列化方式，用特殊字符表示孩子是null，然后先序遍历，可以唯一表示一棵子树。

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func findDuplicateSubtrees(root *TreeNode) []*TreeNode {    a:=make(map[string]int)    a1,tn:=serllize(root,a)    fmt.Println(a1)    return tn}
func serllize(root *TreeNode,s map[string]int)(map[string]int,[]*TreeNode ){    var tn []*TreeNode     if root==nil{        return s,tn    }    s1:=ts(root)    s[s1]++    if s[s1]==2{        tn=append(tn,root)    }    sl,l:=serllize(root.Left,s)    sr,r:=serllize(root.Right,sl)    tn=append(tn,l...)    tn=append(tn,r...)    return sr,tn}
func ts(root *TreeNode)(string){    s:="*"    if root!=nil{        s+=fmt.Sprintf("%d",root.Val)+","        l:=ts(root.Left)        s+=l        r:=ts(root.Right)        s+=r    }    return s}