python二叉樹(shù)怎樣尋找重復(fù)的子樹(shù)

發(fā)布時(shí)間：2021-12-13 16:18:38 來(lái)源：億速云閱讀：199 作者：柒染欄目：大數(shù)據(jù)

這篇文章給大家介紹python二叉樹(shù)怎樣尋找重復(fù)的子樹(shù)，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

給定一棵二叉樹(shù)，返回所有重復(fù)的子樹(shù)。對(duì)于同一類的重復(fù)子樹(shù)，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。

兩棵樹(shù)重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值。

示例 1：

下面是兩個(gè)重復(fù)的子樹(shù)：

2
     /
    4

和

因此，你需要以列表的形式返回上述重復(fù)子樹(shù)的根結(jié)點(diǎn)。

解題思路：

1，重復(fù)子樹(shù)意思是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)一樣

2，重復(fù)多次只取一個(gè)，所以用hash存次數(shù)，取次數(shù)為2的作為解雇

3，雖然前序＋中序遍歷可以恢復(fù)二叉樹(shù)，但是對(duì)于元素值相同的不同二叉樹(shù)，前序，中序遍歷結(jié)果是一樣的，沒(méi)法區(qū)分。

0 和 0

／ \

0 0

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

/** * 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}

關(guān)于python二叉樹(shù)怎樣尋找重復(fù)的子樹(shù)就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

向AI問(wèn)一下細(xì)節(jié)

python二叉樹(shù)怎樣尋找重復(fù)的子樹(shù)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽