バイナリツリーを反転する golang プログラムを実装する方法

バイナリ ツリーの反転 golang

バイナリ ツリーの反転はアルゴリズムに関する古典的な質問であり、インタビューでもよく聞かれます。この記事では、バイナリツリーを反転する golang プログラムを実装します。

バイナリ ツリーとは

バイナリ ツリーは、ルート ノードを含む限られたノードのセットで構成され、各ノードがそれぞれ左側と右側の子に接続されたツリー構造です。 .ノード。すべてのノードに左右の子ノードがない場合、そのツリー構造は二分木と呼ばれます。

golang では、バイナリ ツリー ノードを表すために構造体がよく使用されます。例:

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

上記のコードを使用してバイナリ ツリー ノードを定義します。Val はノードの値を表し、Left はノードの値を表します。 Right は左側の子ノードを表し、Right は右側の子ノードを表します。

バイナリ ツリーを反転する方法

バイナリ ツリーを反転する問題は単純に見えますが、実際にはいくつかの複雑な問題が含まれています。説明の便宜上、次のような二分木があると仮定します。

4
/ \
2 7

 / \
6   9

反転後の二分木は次のようになります。

 4

/ \
7 2
/ \
9 6

コードの実装に関しては、再帰的メソッドを使用してこの問題を解決できます。再帰的メソッドは、構造体のポインタを直接使用して、左右の子ノードの位置を交換できます。再帰メソッドのコードは次のとおりです。

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

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

}

invertTree という名前の関数を宣言します。 , この関数は、バイナリ ツリーのルート ノードへのポインタをパラメータとして受け取り、反転された新しいバイナリ ツリーへのポインタを返します。ルートノードが空の場合は nil が返されます。

関数本体内では、ルートノードの左側の子ノードと右側の子ノードを交換し、この処理を子ノードに再帰的に適用してバイナリツリーを反転する処理を再帰的に実行しています。 。

最後に、反転された新しいバイナリ ツリーのルート ノード ポインタを返します。

完全なコードは次のとおりです:

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

}

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)

}

at この例では、最初にバイナリ ツリーのルート ノードを定義します。 main 関数では、invertTree 関数を呼び出してバイナリ ツリーを反転します。最後に、反転前後の二分木を出力します。

結論

この記事では、二分木を反転する方法についての golang プログラムを紹介しました。単純な再帰関数を使用することで、私たちのプログラムはこの問題をうまく解決できます。この記事がバイナリ ツリー反転の問題と golang 言語の使用を誰もが理解するのに役立つことを願っています。

以上がバイナリツリーを反転する golang プログラムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。