99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

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

創(chuàng)新互聯(lián)是一家專業(yè)提供武鳴企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、成都做網(wǎng)站、H5技術(shù)、小程序制作等業(yè)務(wù)。10年已為武鳴眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進行中。

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

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

示例 1：

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

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

2
    /
   4

和

4

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

解題思路：

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

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

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

   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}

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