【LeetCode】107. Binary Tree Level Order Traversal II 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, BFS(幅優先探索)
2. 解答2：
メモ・参考・感想

問題

原文

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

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]

1
2

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1] Output: [[1]]

1
2

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = [] Output: []

1
2

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].

-1000 <= Node.val <= 1000

内容

二分木rootが与えられるので、葉ノードから順に各ノードの値を返してください。

(左から右に、各階層ごとの葉ノードを返してください。)

※正しくない可能性があります。

解答

解答1：Python, BFS(幅優先探索)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        answer = []
        #dequeを使ってキューを作る。最初と最後の要素へのアクセスがO(1)で可能。
        #キューを使って処理する場合には都合が良い。
        q = deque()
        #二分木をqueueに入れる。
        q.append(root)
        #print(q)
        #キューに要素がある限り繰り返す
        while q:
            #現在探索中の階層にある各ノードを入れるリスト
            current_level = []
            #キューの要素の数だけ繰り返す
            for i in range(len(q)):
                #キューから要素を取り出す。この時、キューからは取り出した要素がなくなる
                _ = q.popleft()
                #キューから取り出した要素がNullでない場合
                #if文内で各ノードの左右の子ノードをキューに入れているが、葉ノードの場合はNullが入る。
                #Nullの場合はTreeNodeクラスの属性であるval,left,rightは持たないのでNone判定になる。
                if _ :
                    current_level.append(_.val)
                    q.append(_.left)
                    q.append(_.right)             
            if current_level:
                answer.append(current_level)
        return answer[::-1]

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:

answer = []

#dequeを使ってキューを作る。最初と最後の要素へのアクセスがO(1)で可能。

#キューを使って処理する場合には都合が良い。

q = deque()

#二分木をqueueに入れる。

q.append(root)

#print(q)

#キューに要素がある限り繰り返す

while q:

#現在探索中の階層にある各ノードを入れるリスト

current_level = []

#キューの要素の数だけ繰り返す

for i in range(len(q)):

#キューから要素を取り出す。この時、キューからは取り出した要素がなくなる

_ = q.popleft()

#キューから取り出した要素がNullでない場合

#if文内で各ノードの左右の子ノードをキューに入れているが、葉ノードの場合はNullが入る。

#Nullの場合はTreeNodeクラスの属性であるval,left,rightは持たないのでNone判定になる。

if _ :

current_level.append(_.val)

q.append(_.left)

q.append(_.right)

if current_level:

answer.append(current_level)

return answer[::-1]

解答2：

メモ・参考・感想

前：2351. First Letter to Appear Twice

次：637. Average of Levels in Binary Tree

LeetCode 解答・解説記事一覧