go語(yǔ)言算法題解二叉樹的拷貝、鏡像和對(duì)稱
更新時(shí)間：2023年01月12日 15:54:39 作者：Hann?Yang
這篇文章主要為大家詳細(xì)介紹了go語(yǔ)言算法題解二叉樹的拷貝、鏡像和對(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
過(guò)程與復(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ò)？
到此這篇關(guān)于go語(yǔ)言算法題解二叉樹的拷貝、鏡像和對(duì)稱的文章就介紹到這了,更多相關(guān)go之二叉樹的拷貝、鏡像和對(duì)稱內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
簡(jiǎn)單聊聊為什么說(shuō)Go語(yǔ)言字符串是不可變的
最近有讀者留言說(shuō)，平時(shí)在寫代碼的過(guò)程中，是會(huì)對(duì)字符串進(jìn)行修改的，但網(wǎng)上都說(shuō) Go 語(yǔ)言字符串是不可變的，這是為什么呢，本文就來(lái)和大家簡(jiǎn)單講講2023-05-05
Channel和goroutine的結(jié)合是Go并發(fā)編程的大殺器。而Channel的實(shí)際應(yīng)用也經(jīng)常讓人眼前一亮，通過(guò)與select，cancel，timer等結(jié)合，它能實(shí)現(xiàn)各種各樣的功能。接下來(lái)，我們就要梳理一下GoLang?channel底層代碼實(shí)現(xiàn)2022-10-10
golang連接kafka消費(fèi)進(jìn)ES操作
這篇文章主要介紹了golang連接kafka消費(fèi)進(jìn)ES操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12
內(nèi)存泄漏是編程中常見的問題,會(huì)對(duì)程序的性能和穩(wěn)定性產(chǎn)生嚴(yán)重影響,本文將深入詳解?Golang?中的內(nèi)存泄漏的原因、檢測(cè)方法以及避免方法,希望對(duì)大家有所幫助2023-12-12
Mac上Go環(huán)境和VS Code的正確安裝與配置方法
Go語(yǔ)言是一個(gè)新興的語(yǔ)言。下面介紹一下如何在Mac系統(tǒng)下安裝和使用這個(gè)語(yǔ)言，Go語(yǔ)言提供了mac下安裝包，可直接下載安裝包點(diǎn)擊安裝2018-03-03
在日常開發(fā)中,我們經(jīng)常需要處理 ZIP 文件,本文主要為大家介紹一個(gè)使用 Go 語(yǔ)言編寫的高效 ZIP 文件解壓工具,希望對(duì)大家有一定的幫助2025-03-03
這篇文章主要介紹了Go語(yǔ)言的變量定義詳情,go定義變量的方式和c,c++,java語(yǔ)法不一樣,var?變量名類型,var在前，變量名在中間，類型在后面,下文更多詳細(xì)內(nèi)容需要的小伙伴可以參考一下2022-03-03
Go語(yǔ)言在Linux環(huán)境下輸出彩色字符的方法
這篇文章主要介紹了Go語(yǔ)言在Linux環(huán)境下輸出彩色字符的方法,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-04-04
實(shí)時(shí)通信的服務(wù)器推送機(jī)制 EventSource(SSE) 簡(jiǎn)介附go實(shí)現(xiàn)示例代碼
EventSource是一種非常有用的 API,適用于許多實(shí)時(shí)應(yīng)用場(chǎng)景,它提供了一種簡(jiǎn)單而可靠的方式來(lái)建立服務(wù)器推送連接,并實(shí)現(xiàn)實(shí)時(shí)更新和通知,這篇文章主要介紹了實(shí)時(shí)通信的服務(wù)器推送機(jī)制 EventSource(SSE)簡(jiǎn)介附go實(shí)現(xiàn)示例,需要的朋友可以參考下2024-03-03
go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實(shí)現(xiàn)示例
這篇文章主要為大家介紹了go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07