【アルゴリズム脳トレ】leetcode medium 102 binary tree level order traversal

こんにちは

今回の学びは

・level orderといわれたらbfsの問題

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

これはlevel orderといわれたらbfsの問題です。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　

O(n)で

実際の実装はこちら

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None: return []
        stack = [root]
        ans = []
        while len(stack) > 0:
            another_stack = []
            leveled_nodes = []
            while len(stack) > 0:
                node = stack.pop(0)
                if node != None:
                    leveled_nodes.append(node.val)
                if node.left: another_stack.append(node.left)
                if node.right: another_stack.append(node.right)
            ans.append(leveled_nodes)
            stack.extend(another_stack)
        return ans

実装後です。timespace analysis (時間とスペースの分析）は　◯◯

todo: list extend の実行時間をしらべておきましょう => pythonのしくみ

まとめ

・level orderといわれたらbfsの問題

以上です