golang 二分木の各層を横断する方法

2年 ago
海斗, 葵
1 minute

二分木の幅優先探索（BFS）を実現するには、キューを使用して実装します。

まず、二分木の構造を定義します：

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

その場合、キューを使用して階層の探索をサポートできます。

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}

この関数はまずルートノードが空でないか調べ、もし空であれば、空の結果を直接返します。

次に、キューを作成し、根のノードをキューに追加します。

キューが空になるまでループを回し、その間キューのサイズを記録して階層のノード数を記録する必要があります。

キューから現在の階層のノードを取り出して、その値をその階層の結果配列に追加します。次に、そのノードの左と右の子ノードをキューに追加して、次の階層の探索に備えます。

最後に、その階層の結果の配列を最終結果の配列に加えます。

最後に結果の配列を返せば、二叉木の階層的なトラバースの結果となります。

なお、上記のコードは一例であり、実際の利用にあたっては実装方法が異なる可能性があります。

bannerAds