如何實作一個翻轉二叉樹的golang程序

翻轉二元樹 golang

二元樹翻轉是一道經典的演算法問題，在面試中也常被問到。在本文中，我們將實作一個翻轉二元樹的golang程式。

什麼是二元樹

二元樹是一種樹狀結構，它由一組有限的節點組成，這些節點包括一個根節點，以及每個節點分別連接到左和右子節點。當所有節點都沒有左或右子節點時，樹狀結構就稱為二元樹。

在golang中，常使用結構體來表示二元樹節點。例如：

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

我們使用以上程式碼定義一個二元樹節點，其中Val表示節點的值，Left表示左子節點，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)

}

在在本例中，我們首先定義了一棵二元樹的根節點。在主函數中，我們呼叫invertTree函數，翻轉這棵二元樹。最後，我們列印出翻轉前和翻轉的二元樹。

結論

在本文中，我們展示如何翻轉二元樹的golang程式。透過使用一個簡單的遞歸函數，我們的程式能夠很好地完成該問題。希望這篇文章對大家了解二元樹翻轉問題以及golang語言的使用有幫助。

以上是如何實作一個翻轉二叉樹的golang程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！