go語言算法題解二叉樹的拷貝、鏡像和對(duì)稱
更新時(shí)間：2023年01月12日 15:54:39 作者：Hann?Yang
這篇文章主要為大家詳細(xì)介紹了go語言算法題解二叉樹的拷貝、鏡像和對(duì)稱，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
拷貝副本
復(fù)制一個(gè)二叉樹副本，廣度優(yōu)先遍歷同時(shí)設(shè)置兩個(gè)隊(duì)列，一個(gè)遍歷一個(gè)復(fù)制創(chuàng)建。
func Copy(bt *biTree) *biTree {
root := bt.Root
if root == nil {
return &biTree{}
}
node := &btNode{Data: root.Data}
Queue1, Queue2 := []*btNode{root}, []*btNode{node}
for len(Queue1) > 0 {
p1, p2 := Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
Node := &btNode{Data: p1.Lchild.Data}
p2.Lchild = Node
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, Node)
}
if p1.Rchild != nil {
Node := &btNode{Data: p1.Rchild.Data}
p2.Rchild = Node
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, Node)
}
}
return &biTree{Root: node}
}相同二叉樹
遞歸法
func Equal(bt1, bt2 *btNode) bool {
if bt1 == nil && bt2 == nil {
return true
} else if bt1 == nil || bt2 == nil {
return false
}
if bt1.Data != bt2.Data {
return false
}
return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
func (bt *biTree) Equal(bt2 *biTree) bool {
return Equal(bt.Root, bt2.Root)
}BFS
過程與復(fù)制副本類似，設(shè)置兩個(gè)隊(duì)列，同時(shí)遍歷只要有一處不同即返回不相同。
func (bt *biTree) SameAs(bt2 *biTree) bool {
root1, root2 := bt.Root, bt2.Root
if root1 == nil && root2 == nil {
return true
} else if root1 == nil || root2 == nil {
return false
}
Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
p1, p2 := Queue1[0], Queue2[0]
for len(Queue1) > 0 && len(Queue2) > 0 {
p1, p2 = Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
return false
}
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, p2.Lchild)
} else if p2.Lchild != nil {
if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
return false
}
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, p2.Lchild)
}
if p1.Rchild != nil {
if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
return false
}
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, p2.Rchild)
} else if p2.Rchild != nil {
if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
return false
}
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, p2.Rchild)
}
}
return true
}
鏡像二叉樹
生成一棵二叉樹的鏡像：
遞歸法
func (bt *btNode) InvertNodes() {
if bt != nil {
bt.Lchild.InvertNodes()
bt.Rchild.InvertNodes()
bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
}
}
func (bt *biTree) Mirror() {
bt.Root.InvertNodes()
}BFS
func Mirror(bt *biTree) *biTree {
root := bt.Root
if root == nil {
return &biTree{}
}
node := &btNode{Data: root.Data}
Queue1, Queue2 := []*btNode{root}, []*btNode{node}
for len(Queue1) > 0 {
p1, p2 := Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
Node := &btNode{Data: p1.Lchild.Data}
p2.Rchild = Node
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, Node)
}
if p1.Rchild != nil {
Node := &btNode{Data: p1.Rchild.Data}
p2.Lchild = Node
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, Node)
}
}
return &biTree{Root: node}
}對(duì)稱二叉樹
方法一：判斷左子樹與右子樹的反轉(zhuǎn)是否相等
func (bt *biTree) IsSymmetry() bool {
return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
}方法二：判斷自身與鏡像是否相同
func (bt *biTree) IsSymmetry2() bool {
bt2 := Mirror(bt)
return bt.SameAs(bt2)
}判斷二棵二叉樹是否互為鏡像
方法一：生成其中一棵的鏡像，判斷鏡像與另一棵是否相同
func (bt *biTree) IsMirror(bt2 *biTree) bool {
return bt.SameAs(Mirror(bt2))
}方法二：分別以此二棵樹作左右子樹生成一棵新樹，判斷新樹是否左右對(duì)稱
func (bt *biTree) IsMirror(bt2 *biTree) bool {
root := &biTree{&btNode{1, bt.Root, bt2.Root}}
return root.IsSymmetry()
}包biTree函數(shù)匯總
至此，《數(shù)據(jù)結(jié)構(gòu)：二叉樹》系列（1~3）已累積了從創(chuàng)建、遍歷等功能的20多個(gè)函數(shù)和方法，匯總?cè)缦拢?/p>
/* The Package biTree
* https://hannyang.blog.csdn.net/article/details/126556548
*
* based on Go program by Hann Yang,
* modified on 2022/8/31.
*/
package biTree
type btNode struct {
Data interface{}
Lchild *btNode
Rchild *btNode
}
type biTree struct {
Root *btNode
}
func Build(data interface{}) *biTree {
var list []interface{}
if data == nil {
return &biTree{}
}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) == 0 {
return &biTree{}
}
node := &btNode{Data: list[0]}
list = list[1:]
Queue := []*btNode{node}
for len(list) > 0 {
if len(Queue) == 0 {
//panic("Given array can not build binary tree.")
return &biTree{Root: node}
}
cur := Queue[0]
val := list[0]
Queue = Queue[1:]
if val != nil {
cur.Lchild = &btNode{Data: val}
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
}
list = list[1:]
if len(list) > 0 {
val := list[0]
if val != nil {
cur.Rchild = &btNode{Data: val}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
list = list[1:]
}
}
return &biTree{Root: node}
}
func Create(data interface{}) *biTree {
var list []interface{}
btree := &biTree{}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) > 0 {
btree.Root = &btNode{Data: list[0]}
for _, data := range list[1:] {
btree.AppendNode(data)
}
}
return btree
}
func (bt *biTree) Append(data interface{}) {
var list []interface{}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) > 0 {
for _, data := range list {
bt.AppendNode(data)
}
}
}
func (bt *biTree) AppendNode(data interface{}) {
root := bt.Root
if root == nil {
bt.Root = &btNode{Data: data}
return
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
} else {
cur.Lchild = &btNode{Data: data}
return
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
} else {
cur.Rchild = &btNode{Data: data}
break
}
}
}
func (bt *biTree) Levelorder() []interface{} { //BFS
var res []interface{}
root := bt.Root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
res = append(res, cur.Data)
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
return res
}
func (bt *biTree) BForder2D() [][]interface{} {
var res [][]interface{}
root := bt.Root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
Nodes := []interface{}{}
Levels := len(Queue)
for Levels > 0 {
cur := Queue[0]
Queue = Queue[1:]
Nodes = append(Nodes, cur.Data)
Levels--
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
res = append(res, Nodes)
}
return res
}
func (bt *biTree) Preorder() []interface{} {
var res []interface{}
cur := bt.Root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
res = append(res, cur.Data)
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}
func (bt *biTree) Inorder() []interface{} {
var res []interface{}
cur := bt.Root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
res = append(res, cur.Data)
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}
func (bt *biTree) Postorder() []interface{} {
var res []interface{}
if bt.Root == nil {
return res
}
cur, pre := &btNode{}, &btNode{}
Stack := []*btNode{bt.Root}
for len(Stack) > 0 {
cur = Stack[len(Stack)-1]
if cur.Lchild == nil && cur.Rchild == nil ||
pre != nil && (pre == cur.Lchild || pre == cur.Rchild) {
res = append(res, cur.Data)
Stack = Stack[:len(Stack)-1]
pre = cur
} else {
if cur.Rchild != nil {
Stack = append(Stack, cur.Rchild)
}
if cur.Lchild != nil {
Stack = append(Stack, cur.Lchild)
}
}
}
return res
}
func (bt *btNode) MaxDepth() int {
if bt == nil {
return 0
}
Lmax := bt.Lchild.MaxDepth()
Rmax := bt.Rchild.MaxDepth()
return 1 + Max(Lmax, Rmax)
}
func (bt *btNode) MinDepth() int {
if bt == nil {
return 0
}
Lmin := bt.Lchild.MinDepth()
Rmin := bt.Rchild.MinDepth()
return 1 + Min(Lmin, Rmin)
}
func (bt *biTree) Depth() int { //BFS
res := 0
root := bt.Root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
Levels := len(Queue)
for Levels > 0 {
cur := Queue[0]
Queue = Queue[1:]
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
Levels--
}
res++
}
return res
}
func (bt *btNode) Degree() int {
res := 0
if bt.Lchild != nil {
res++
}
if bt.Rchild != nil {
res++
}
return res
}
func (bt *biTree) LeafNodeBFS() []interface{} {
var res []interface{}
root := bt.Root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
//if cur.Lchild == nil && cur.Rchild == nil {
if cur.Degree() == 0 {
res = append(res, cur.Data)
}
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
return res
}
func (bt *biTree) LeafNodeDFS() []interface{} {
var res []interface{}
cur := bt.Root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
//if cur.Lchild == nil && cur.Rchild == nil {
if cur.Degree() == 0 {
res = append(res, cur.Data)
}
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}
func (bt *btNode) InvertNodes() *btNode {
if bt != nil {
bt.Lchild.InvertNodes()
bt.Rchild.InvertNodes()
bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
}
return bt
}
func (bt *biTree) Mirror() {
bt.Root.InvertNodes()
}
func Copy(bt *biTree) *biTree {
root := bt.Root
if root == nil {
return &biTree{}
}
node := &btNode{Data: root.Data}
Queue1, Queue2 := []*btNode{root}, []*btNode{node}
for len(Queue1) > 0 {
p1, p2 := Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
Node := &btNode{Data: p1.Lchild.Data}
p2.Lchild = Node
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, Node)
}
if p1.Rchild != nil {
Node := &btNode{Data: p1.Rchild.Data}
p2.Rchild = Node
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, Node)
}
}
return &biTree{Root: node}
}
func Mirror(bt *biTree) *biTree {
root := bt.Root
if root == nil {
return &biTree{}
}
node := &btNode{Data: root.Data}
Queue1, Queue2 := []*btNode{root}, []*btNode{node}
for len(Queue1) > 0 {
p1, p2 := Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
Node := &btNode{Data: p1.Lchild.Data}
p2.Rchild = Node
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, Node)
}
if p1.Rchild != nil {
Node := &btNode{Data: p1.Rchild.Data}
p2.Lchild = Node
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, Node)
}
}
return &biTree{Root: node}
}
func Max(L, R int) int {
if L > R {
return L
} else {
return R
}
}
func Min(L, R int) int {
if L < R {
return L
} else {
return R
}
}
func Equal(bt1, bt2 *btNode) bool {
if bt1 == nil && bt2 == nil {
return true
} else if bt1 == nil || bt2 == nil {
return false
}
if bt1.Data != bt2.Data {
return false
}
return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
func (bt *biTree) Equal(bt2 *biTree) bool {
return Equal(bt.Root, bt2.Root)
}
func (bt *biTree) SameAs(bt2 *biTree) bool {
root1, root2 := bt.Root, bt2.Root
if root1 == nil && root2 == nil {
return true
} else if root1 == nil || root2 == nil {
return false
}
Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
p1, p2 := Queue1[0], Queue2[0]
for len(Queue1) > 0 && len(Queue2) > 0 {
p1, p2 = Queue1[0], Queue2[0]
Queue1, Queue2 = Queue1[1:], Queue2[1:]
if p1.Lchild != nil {
if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
return false
}
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, p2.Lchild)
} else if p2.Lchild != nil {
if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
return false
}
Queue1 = append(Queue1, p1.Lchild)
Queue2 = append(Queue2, p2.Lchild)
}
if p1.Rchild != nil {
if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
return false
}
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, p2.Rchild)
} else if p2.Rchild != nil {
if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
return false
}
Queue1 = append(Queue1, p1.Rchild)
Queue2 = append(Queue2, p2.Rchild)
}
}
return true
}
func (bt *biTree) MirrorOf(bt2 *biTree) bool {
return bt.SameAs(Mirror(bt2))
}
func (bt *biTree) IsMirror(bt2 *biTree) bool {
root := &biTree{&btNode{1, bt.Root, bt2.Root}}
return root.IsSymmetry()
}
func (bt *biTree) IsSymmetry() bool {
return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
}
func (bt *biTree) IsSymmetry2() bool {
bt2 := Mirror(bt)
return bt.SameAs(bt2)
}另外：從leetcode題目中整理了50多個(gè)與二叉樹相關(guān)的題目，對(duì)照看看還有多少?zèng)]刷過？
到此這篇關(guān)于go語言算法題解二叉樹的拷貝、鏡像和對(duì)稱的文章就介紹到這了,更多相關(guān)go之二叉樹的拷貝、鏡像和對(duì)稱內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了go語言編程之select信道處理示例詳解，<BR>有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-04-04
本文詳細(xì)介紹了Go語言中strings包的基本使用方法,包括字符串的前綴、后綴判斷,字符串包含、索引查找、字符串替換、計(jì)數(shù)、重復(fù)、大小寫轉(zhuǎn)換、修剪、分割、拼接以及數(shù)據(jù)類型轉(zhuǎn)換等功能,示例代碼豐富,適合初學(xué)者和需要使用字符串處理功能的開發(fā)者參考學(xué)習(xí)2024-10-10
這篇文章主要給大家介紹了關(guān)于Go語言中通過Lua腳本操作Redis的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-01-01
利用Go語言實(shí)現(xiàn)流量回放工具的示例代碼
今天給大家推薦一款使用Go語言編寫的流量回放工具?--?goreplay；工作中你一定遇到過需要在服務(wù)器上抓包的場(chǎng)景，有了這個(gè)工具就可以助你一臂之力，廢話不多，我們接下來來看一看這個(gè)工具2022-09-09
本文主要介紹了go語言中g(shù)orm時(shí)間格式化，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
重學(xué)Go語言之如何開發(fā)RPC應(yīng)用
這篇文章主要為大家詳細(xì)介紹了在Go語言中如何構(gòu)建RPC應(yīng)用,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-09-09
在當(dāng)今的軟件開發(fā)領(lǐng)域,多種編程語言常常需要協(xié)同工作,以充分利用各自的優(yōu)勢(shì)來構(gòu)建復(fù)雜的應(yīng)用系統(tǒng),Go 語言作為一門高效、簡(jiǎn)潔的編程語言,也經(jīng)常需要與其他語言進(jìn)行交互,接下來,我們將詳細(xì)探討 Go 語言如何與其他語言進(jìn)行交互,需要的朋友可以參考下2024-06-06
GoLang語法之標(biāo)準(zhǔn)庫(kù)fmt.Printf的使用
fmt包實(shí)現(xiàn)了類似C語言printf和scanf的格式化I/O,主要分為向外輸出內(nèi)容和獲取輸入內(nèi)容兩大部分,本文就來介紹一下GoLang語法之標(biāo)準(zhǔn)庫(kù)fmt.Printf的使用,感興趣的可以了解下2023-10-10
GO語言實(shí)現(xiàn)AES-CFB加密的操作方法
本文介紹了如何用Go語言實(shí)現(xiàn)AES-CFB加密和解密,首先,定義一個(gè)屬于encrypt包的文件,使用AES算法、CFB模式和Base64編碼等功能,在加密函數(shù)中,接收明文和密鑰,生成一個(gè)AES塊密碼和一個(gè)隨機(jī)的初始化向量,實(shí)現(xiàn)明文的加密2024-10-10
Go語言sync包與鎖實(shí)現(xiàn)限制線程對(duì)變量的訪問
本文主要介紹了Go語言sync包與鎖實(shí)現(xiàn)限制線程對(duì)變量的訪問，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04