Bagaimana untuk melaksanakan program golang yang membalikkan pokok binari

Flip Binary Tree golang

Binary tree flipping ialah soalan algoritma klasik dan sering ditanya dalam temu bual. Dalam artikel ini, kami akan melaksanakan program golang yang membalikkan pokok binari.

Apakah pokok binari?

Pokok binari ialah struktur pokok yang terdiri daripada set nod terhad, termasuk nod akar, dan setiap nod disambungkan ke anak kiri dan kanan masing-masing. Apabila semua nod tidak mempunyai nod anak kiri atau kanan, struktur pokok dipanggil pokok binari.

Dalam golang, struktur sering digunakan untuk mewakili nod pokok binari. Contohnya:

taip TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

Kami menggunakan kod di atas untuk mentakrifkan nod pokok binari, dengan Val mewakili nilai nod dan Kiri mewakili nod anak kiri , Kanan mewakili nod anak kanan.

Cara membalikkan pokok binari

Masalah membalikkan pokok binari nampaknya mudah, tetapi ia sebenarnya melibatkan beberapa isu yang rumit. Untuk kemudahan penjelasan, kami mengandaikan bahawa terdapat pokok binari seperti berikut:

4
/
2 7

 / \
6   9

Selepas terbalik, pokok binari hendaklah menjadi :

 4

/
7 2
/
9 6

Dari segi pelaksanaan kod, kita boleh menggunakan kaedah rekursif untuk menyelesaikan masalah ini. Kaedah rekursif boleh terus menggunakan penunjuk struktur untuk menukar kedudukan nod anak kiri dan kanan. Kod kaedah rekursif adalah seperti berikut:

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

Kami mengisytiharkan nama Fungsi invertTree yang menerima penuding nod akar pokok binari sebagai parameter dan mengembalikan penunjuk kepada pokok binari baharu yang terbalik. Jika nod akar kosong, nil dikembalikan.

Di dalam badan fungsi, kami menggunakan rekursi untuk menyelesaikan proses membalikkan pokok binari Kami menukar nod anak kiri dan nod anak kanan nod akar, dan kemudian menggunakan proses ini secara rekursif pada nod anak. .

Akhir sekali, kami mengembalikan penunjuk nod akar pokok binari terbalik yang baharu.

Kod lengkap adalah seperti berikut:

pakej utama

import "fmt"

taip TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

func main() {

root := &TreeNode{Val: 4, Left: &TreeNode{Val: 2},
    Right: &TreeNode{Val: 7, Left: &TreeNode{Val: 6}, 
           Right: &TreeNode{Val: 9}}}

fmt.Println("Before invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Right.Left.Val, root.Right.Right.Val)

invertTree(root)

fmt.Println("After invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Left.Left.Val, root.Left.Right.Val)

}

Dalam contoh ini, kita mula-mula mentakrifkan nod akar pokok binari. Dalam fungsi utama, kami memanggil fungsi invertTree untuk membalikkan pokok binari. Akhirnya, kami mencetak pokok binari sebelum dan selepas membalikkan.

Kesimpulan

Dalam artikel ini, kami menunjukkan program golang tentang cara membalikkan pokok binari. Dengan menggunakan fungsi rekursif mudah, program kami boleh menyelesaikan masalah ini dengan baik. Saya berharap artikel ini dapat membantu semua orang memahami masalah pembalikan pokok binari dan penggunaan bahasa golang.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan program golang yang membalikkan pokok binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!