So implementieren Sie ein Golang-Programm, das einen Binärbaum umdreht

Flip Binary Tree golang

Das Umdrehen von Binärbäumen ist eine klassische Algorithmusfrage und wird häufig in Interviews gestellt. In diesem Artikel implementieren wir ein Golang-Programm, das einen Binärbaum umdreht.

Was ist ein Binärbaum? Ein Binärbaum ist eine Baumstruktur, die aus einer begrenzten Menge von Knoten besteht, einschließlich eines Wurzelknotens, und jeder Knoten ist mit dem linken bzw. rechten untergeordneten Knoten verbunden. Wenn alle Knoten keine linken oder rechten untergeordneten Knoten haben, wird die Baumstruktur als Binärbaum bezeichnet.

In Golang werden Strukturen häufig zur Darstellung binärer Baumknoten verwendet. Zum Beispiel:

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

Wir verwenden den obigen Code, um einen binären Baumknoten zu definieren, wobei Val den Wert des Knotens darstellt, Left den linken untergeordneten Knoten darstellt und Right den rechten untergeordneten Knoten darstellt .

Wie man einen Binärbaum umdreht

Das Problem des Umdrehens eines Binärbaums scheint einfach, beinhaltet aber tatsächlich einige komplexe Probleme. Der Einfachheit halber gehen wir davon aus, dass es einen Binärbaum wie folgt gibt:

4

/

2 7

 / \
6   9

Nach dem Umdrehen sollte der Binärbaum wie folgt aussehen:

 4

/

7 2

/
9 6

In Bezug auf die Codeimplementierung können wir rekursive Methoden verwenden, um dieses Problem zu lösen. Die rekursive Methode kann den Zeiger der Struktur direkt verwenden, um die Positionen des linken und rechten untergeordneten Knotens auszutauschen. Der Code der rekursiven Methode lautet wie folgt:

func invertTree(root

TreeNode)

TreeNode {

if root == nil {
    return nil
}

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

}

Wir haben eine Funktion namens invertTree deklariert, die den Wurzelknotenzeiger eines Binärbaums als Parameter empfängt und zurückgibt ein übergebener Zeiger auf den neuen Binärbaum, der umgedreht wird. Wenn der Wurzelknoten leer ist, wird Null zurückgegeben.

Im Funktionskörper verwenden wir die Rekursion, um den Prozess des Umdrehens des Binärbaums abzuschließen. Wir tauschen den linken untergeordneten Knoten und den rechten untergeordneten Knoten des Wurzelknotens aus und wenden diesen Prozess dann rekursiv auf die untergeordneten Knoten an.

Schließlich geben wir den Wurzelknotenzeiger des neuen umgedrehten Binärbaums zurück.

Der vollständige Code lautet wie folgt:

package main

import „fmt“

type 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

}

f unc 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)

}

In diesem Beispiel definieren wir zunächst den Wurzelknoten eines Binärbaums. In der Hauptfunktion rufen wir die Funktion invertTree auf, um den Binärbaum umzudrehen. Zum Schluss drucken wir den Binärbaum vor und nach dem Umdrehen aus.

Fazit

In diesem Artikel haben wir ein Golang-Programm zum Umdrehen eines Binärbaums gezeigt. Durch die Verwendung einer einfachen rekursiven Funktion kann unser Programm dieses Problem sehr gut lösen. Ich hoffe, dass dieser Artikel jedem hilft, das Problem des Umdrehens von Binärbäumen und die Verwendung der Golang-Sprache zu verstehen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie ein Golang-Programm, das einen Binärbaum umdreht. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!