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