、バイナリーツリーのDFSについて例題を通して学びましたが、これは実際には一方向にずっとトラバースしていくものです。ツリー内のデータに、高さに従って1層ずつアクセスすることはできるでしょうか？もちろんできます。本節のBFSは、幅優先探索とも呼ばれます。
今でも例を通して説明しています。
トピック分析
| バイナリツリーが与えられた場合、そのノード値を階層的に走査して返します。 |
例
二分木が与えられている[3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
階層走査の結果を返す：[[3],[9,20],[15,7]]
BFS入門
BFS、まず幅を広げること。これは、各層を上から下へ走査してから次の層を走査するということです。ツリーが次のようなものだとします：
BFSによると、アクセス順は以下の通り：
BFSを理解することから、この問題の分析が始まります。
再帰的解法
もう一度、この問題の再帰的な解決策を考えてみましょう。再帰というと、一般的にはまずDFSを思い浮かべます。バイナリツリーの先行順序探索を実行すると同時に、ノードが配置されている階層のレベルを記録して、各レベルの配列を定義し、アクセスされたノードの値を対応するレベルの配列に配置します。
与えられた2進木が[3,9,20,null,null,15,7]だとします：
以上の分析に基づき、コードは以下の通り：
func levelOrder(root *TreeNode) [][]int {
return dfs(root, 0, [][]int{})
}
func dfs(root *TreeNode, level int, res [][]int) [][]int {
if root == nil {
return res
}
if len(res) == level {
res = append(res, []int{root.Val})
} else {
res[level] = append(res[level], root.Val)
}
res = dfs(root.Left, level+1, res)
res = dfs(root.Right, level+1, res)
return res
}
BFSの解法
上記の解決策は、実はバイナリーツリーBFSを実装するためにDFSメソッドを使用することと等価です。では、この問題を解決するためにBFSメソッドを直接使用することはできるのでしょうか？もちろん、Queueデータ構造を使うことができます。ルートノードをキューに初期化し、テールを消費してヘッドを挿入することでBFSを完成させます。
手順を以下に示します：
以上の分析に基づき、コードは以下の通り：
func levelOrder(root *TreeNode) [][]int {
var result [][]int
if root == nil {
return result
}
// 双方向キューを定義する
queue := list.New()
// ルートノードへのヘッダー挿入
queue.PushFront(root)
// 幅の広い検索を実行する
for queue.Len() > 0 {
var current []int
listLength := queue.Len()
for i := 0; i < listLength; i++ {
// テールを消費する
// queue.Remove(queue.Back()).(*TreeNode)最後の要素を取り除き、TreeNode型に変換する。
node := queue.Remove(queue.Back()).(*TreeNode)
current = append(current, node.Val)
if node.Left != nil {
//ヘッダーを挿入する
queue.PushFront(node.Left)
}
if node.Right != nil {
queue.PushFront(node.Right)
}
}
result = append(result, current)
}
return result
}
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。
