LeetCode/Binary Tree Level Order Traversal II

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 이 m / p 로b ぇ ms / 비나 ry-t 에- ょ ]

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 해법 저 것.
처리를 실시하는 순서 대기의 리스트 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