Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
使用した概念BFS
アプローチ
思考
- BFS で各レベルの要素の値を取得する
- 各レベルの最後の値だけを result に格納する
- queue がなくなるまで繰り返す
- この解法には無駄がある
- レベルごとに
level配列を作って全ノードの値を持っている - 本当に欲しいのは末尾の 1 個だけ
- レベルごとに
実装
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level:
result.append(level[-1])
return resultTime Space