python二叉树怎样寻找重复的子树
这篇文章给大家介绍python二叉树怎样寻找重复的子树，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
创新互联是一家专业提供武鸣企业网站建设,专注与成都网站建设、成都做网站、H5技术、小程序制作等业务。10年已为武鸣众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
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 []*TreeNodeif 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+=lr:=ts(root.Right)s+=r}return s}
关于python二叉树怎样寻找重复的子树就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
网站栏目：python二叉树怎样寻找重复的子树
URL地址：http://6mz.cn/article/jiiioh.html