いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】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の問題

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.