【LeetCode】 102. Binary Tree Level Order Traversal 解答・解説【Python】

はじめに
1. ポイント
2. この記事で得られること
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, 幅優先探索(先巡走査：pre order traversal)
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 幅優先探索

この記事で得られること

- 幅優先探索の初歩的な問題の練習
- 幅優先探索(先巡走査：pre-order-traversal)の実装方法

詳細

問題

原文

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

1
2

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

1
2

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = [] Output: []

1
2

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].

-1000 <= Node.val <= 1000

内容(和訳)

二分木rootが与えられるので、階層ごとに走査して値を返してください。

※正しくない可能性があります。

解答

解答1：Python, 幅優先探索(先巡走査：pre order traversal)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        #Existence check
        if not root: return None

        #Make queue from root
        from collections import deque
        queue = deque()
        queue.append(root)
        
        #BFS
        answer = []
        while queue:
            current_level_nodes = []
    
            for i in range(len(queue)):
                node = queue.popleft()
                if node:
                    #When node.val is 0, ↓ It is judged as False, so current_level_nodes is not assigned any value. 
                    #if node.val: current_level_nodes.append(node.val)
                    if node: current_level_nodes.append(node.val)
                    if node.left: queue.append(node.left)
                    if node.right: queue.append(node.right)
            if current_level_nodes:
                answer.append(current_level_nodes)

        #return
        return answer

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

#Existence check

if not root: return None

#Make queue from root

from collections import deque

queue = deque()

queue.append(root)

#BFS

answer = []

while queue:

current_level_nodes = []

for i in range(len(queue)):

node = queue.popleft()

if node:

#When node.val is 0, ↓ It is judged as False, so current_level_nodes is not assigned any value.

#if node.val: current_level_nodes.append(node.val)

if node: current_level_nodes.append(node.val)

if node.left: queue.append(node.left)

if node.right: queue.append(node.right)

if current_level_nodes:

answer.append(current_level_nodes)

#return

return answer

はじめに、rootに木がない場合はNoneを返します。

木がある場合は、幅優先探索に必要なキューを作ります。

collectionsからdequeをインポートしてdeque()でキューを作成後、

クラスTreeNodeのインスタンスとして入力されるrootを追加します。

BFSの部分では、queueにノードがある限り処理を繰り返します。

・最初の時点では木の根ノードだけが入っています。

while文の中で根ノードから2層目の子ノード(最大2つ)がそれぞれ代入され、

2層目の走査中に3層目の子ノード(最大4つ)がそれぞれ代入されます。

※各ノードが子を持たない場合は、queueには何も代入されません。

・各層の走査を開始するときに、現在の階層にある全ノードの値を保持するためのリストを準備しています。→current_level_nodes

現在の階層の操作が終了したら、この問題の解答であるanswerにリストとして追加されます。

・for文では、現在queueに入っている要素を一巡して走査します。

while文の一週目(第一階層の走査)では、根ノードしかないので1回のみ

while文の二週目(第二階層の走査)では、根ノードの左右の子ノードを走査するので最大2回

while文の三週目(第三階層の走査)では、根ノードの孫ノードを走査するので最大4回走査します。

queueから1つずつノードを取り出すので、for文のループ変数はnodeにしています。

nodeがnullでなければ、以下の操作を行います。

→値をcurrent_level_nodesに追加

→左の子ノードがあればqueueに追加

→右の子ノードがあればqueueに追加

葉ノードの場合は左右の子ノードがありません。

current_level_nodesをanswerに入れてfor文の1回の走査は終了です。

これを繰り返します。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は他の問題もどうぞ

前：142. Linked List Cycle II

次：98. Validate Binary Search Tree

LeetCode 解答・解説記事一覧