NeetCodeのSolutionを書いていく

#

Binary Tree Level Order Traversal

#

問題

#

２分木のルートが与えられます。 階層順にネストしたリストとして返しなさい。 各リストは左から右の順番に格納します。

例

#

Input: root = [1,2,3,4,5,6,7] Output: [[1],[2,3],[4,5,6,7]]

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

Input: root = [] Output: []

制約

#

• 0 <= The number of nodes in both trees <= 1000.
• -1000 <= Node.val <= 1000

計算量：O(n) メモリ：O(n)

メモ

#

どうやって配列から２分木を決定するんだろう。完全２分木なのか？ 特にあたって問題文に記載がない条件が出てきた。 Noneは有効なデータであって、そこの枝はないという意味らしい。 これってすごく大事な説明なんじゃ・・・？

解き方としてはrootから処理を開始して、レベルごとに値を配列に格納していけばいいらしい。 言葉にするとそのままなんだけど、それをどうやるかということで。 レベルごとに、次のレベルをキューに詰めながら処理をすると良いらしい。

import collections
from typing import List, Optional


# 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]]:
        res = []

        q = collections.deque()
        q.append(root)

        while q:
            qLen = len(q)
            level = []
            for i in range(qLen):
                node = q.popleft()
                if node:
                    level.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            if level:
                res.append(level)

        return res