【アルゴリズム脳トレ】leetcode easy 107 binary tree level order traversal ii

こんにちは

今回の学びは

・pythonリストの参照は安いがinsertは高い、とおぼえておこう。delも高い。

・sliceのコストはたかだかO(start-(stop))

・O(N)がループの外に来るなら、高そうなsliceも実は許容できうる

問題はhttps://leetcode.com/problems/binary-tree-level-order-traversal-ii/

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

４、実装しましょう。

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if root is None: return []
        
        stack, order = [root], []
        while len(stack) > 0:
            layer_stack = []
            layer_order = []
            for node in stack:
                layer_order.append(node.val)
                if node.left: layer_stack.append(node.left)
                if node.right: layer_stack.append(node.right)
            
            #order.append(layer_order)
            order.insert(0, layer_order)
            stack = layer_stack
        return order

上の実装でクリアできます。

しかしながらtime complexityはO(N)えはありません。

O(N^2)になっています。

なぜでしょうか？

それはinsert(0, xxx)自体がO(N)なので全体ではO(N^2)となってしまっている

という訳です。

私もdiscussionで彼の指摘を見るまでは気にもしませんでした。

The complexity of insert is O(N), which makes the solution O(N^2).
So I changed it as follows:

quoted from https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/34978/Python-solutions-(dfs-recursively-dfs%2Bstack-bfs%2Bqueue).

たしかに

python listのinsertのtime complexityは最悪のケースはindexが0のときでO(N)となっている。(元記事)

python-wikiにもそうある。

上図出典:https://wiki.python.org/moin/TimeComplexity

参考stackoverflow: what-is-the-cost-complexity-of-insert-in-list-at-some-location

これは大事な気付きだったのでpythonの仕組みに追加した。

・pythonリストの参照は安いがinsertは高い、とおぼえておこう。delも高い。

だったらどう実装する？

１例はこちら（出典 source code :link)

class Solution:
    def levelOrderBottom(self, root):
        res, queue = [], [root]
        while queue:
            res.append([node.val for node in queue if node])
            queue = [
                child for node in queue if node
                for child in (node.left, node.right)
            ]
        return res[-2::-1]

この実装では最後のres[-2::-1]で、list[start:stop:step]に後ろから二番目から一個づつ手前に配列を生成しており、ここで順番を逆にしています。python のsliceのコストはO(start-(stop))ですが、forループの外でこの操作をしているので、最初の実装より速くO(N)、ということになります。O(N)がループの外に来るなら、高そうなsliceも実は許容できるということを学べた経験です。

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは？」

逆にするのはsliceで最後に。

まとめ

・pythonリストの参照は安いがinsertは高い、とおぼえておこう。delも高い。

・sliceのコストはたかだかO(start-(stop))

・O(N)がループの外に来るなら、高そうなsliceも実は許容できうる

以上です