NeetCodeのSolutionを書いていく #
Binary Tree Right Side View #
https://neetcode.io/problems/binary-tree-right-side-view
neetcode.io
問題 #
２分木のルートが与えられます。 右側から見える値を上から下の順番で返しましょう。
例 #
Input: root = [1,2,3] Output: [1,3]
Input: root = [1,2,3,4,5,6,7] Output: [1,3,7]
制約 #
- 0 <= number of nodes in the tree <= 100
- -100 <= Node.val <= 100
- 計算量：O(n)
- メモリ：O(n)
メモ #
右を追跡して、右がNoneになるまでリストにappendしながら繰り返せばよいだけでは？ いや、ポイントは「右から見える」だ。 つまり、右のノードがない場合は右から見て左のノードが見えるよね、ってことか。
平衡二分探索木を前提とすれば、右を追跡、最後の値を追記、でいけそう。
もっといい方法は幅優先探索で、右(最後の値)をappendして返す形でした。
import collections
from typing import List, Optional
# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ret: List[int] = []
if not root:
return ret
q: collections.deque[TreeNode] = collections.deque()
q.append(root)
while q:
last_value: int = 101
l = len(q)
for _ in range(l):
node = q.popleft()
if node:
last_value = node.val
q.append(node.left)
q.append(node.right)
if last_value != 101:
ret.append(last_value)
return ret