LeetCode / Binary Tree Level Order Traversal II

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

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

Binary Tree Level Order Traversal "II"ということで"I"はどこいったんだという話ですが、"I"が難易度medium、"II"がeasyという謎順序になっているので、"II"から記事にします。

解答・解説

解法1

recursiveな解法。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        res = []
        self.dfs(root, 0, res)
        return res

    def dfs(self, root, level, res):
        if root:
            if len(res) < level + 1: # n階層目に初めて到達したときにはリストを1つ追加する（n階層目にはn個のリストがあるなので、それより少ない場合は追加する）
                res.insert(0, []) # index0にリストを追加。こうすることで追加済みリストが古いものほど後ろになる（最後に全体をreverseする必要がない）
            res[-(level+1)].append(root.val)
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level+1, res)

解法2

Iterativeな解法その1。
処理を行う順番待ちのリストqueueを作ってやり、そこにnode.left, node.rightを格納するIterationを回します。

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        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]

細かな工夫として、root=[]でも全く同一のコードで処理できるように、res[-2::-1]でリストをreverseした上で初めの要素を削除する処理としています。

解法3

Iterativeな解法その2。
型はdeque型ですが、順番待ちのリストqueueを作り、そこにnode.left, node.rightを格納するIterationを回すというやり方は解法2と全く同じです。
かつ、if node 以降の処理は解法1の考え方と同じ。
解法1と同様、最後にリストをreverseする必要がないのが計算量の点で優れています。

from collections import deque
class Solution:
    def levelOrderBottom(self, root):
        queue, res = deque([(root, 0)]), []
        while queue:
            node, level = queue.popleft()
            if node:
                if len(res) < level+1:
                    res.insert(0, [])
                res[-(level+1)].append(node.val)
                queue.append((node.left, level+1))
                queue.append((node.right, level+1))
        return res