用 Golang 實現 BFS 遍歷二叉樹

二叉樹是一種常用的數據結構，它在計算機科學中有着廣泛的應用。BFS（Breadth First Search）算法是一種用於遍歷樹或圖的算法，它從根節點開始，逐層遍歷每個節點，直到找到目標節點或遍歷完整個樹。下面是用 Golang 實現 BFS 遍歷二叉樹算法的示例代碼：

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func bfsTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    result := []int{}
    for len(queue) > 0 {
        levelLength := len(queue)
        for i := 0; i < levelLength; i++ {
            node := queue[0]
            queue = queue[1:]
            result = append(result, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

在這個示例代碼中，我們定義了一個 TreeNode 結構體，它表示二叉樹中的一個節點，包含一個整數 Val，以及左右子樹的指針 Left 和 Right。我們還定義了一個 bfsTraversal 函數，它接受一個根節點作爲參數，返回一個整數數組，表示 BFS 遍歷的結果。

在函數中，我們首先判斷根節點是否爲空，如果是，直接返回一個空數組。然後我們創建一個隊列 queue，將根節點加入隊列中。接着我們創建一個空數組 result，用於存儲遍歷的結果。我們使用一個循環來遍歷隊列中的所有節點，每次循環遍歷一層節點。我們使用一個變量 levelLength 來記錄當前層的節點數，然後從隊列中取出 levelLength 個節點，並將它們的 Val 加入到 result 數組中。同時，如果節點有左右子樹，我們就將它們加入到隊列中。最後，返回 result 數組，即爲 BFS 遍歷的結果。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/SWESAPglUFDFR8OYINC_cQ