問題
原文
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:
12 Input: root = [3,9,20,null,null,15,7]Output: [[15,7],[9,20],[3]]Example 2:
12 Input: root = [1]Output: [[1]]Example 3:
12 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(幅優先探索)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# 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
コメント