NeetCode 150 [Trees]medium:Binary Tree Level Order Traversal

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