溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹python二叉樹怎樣尋找重復的子樹，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
給定一棵二叉樹，返回所有重復的子樹。對于同一類的重復子樹，你只需要返回其中任意一棵的根結點即可。
兩棵樹重復是指它們具有相同的結構以及相同的結點值。
示例 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二叉樹怎樣尋找重復的子樹就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
