NeetCode 150 [Trees]medium:Binary Tree Right Side View

NeetCodeのSolutionを書いていく

Binary Tree Right Side View

問題

２分木のルートが与えられます。
右側から見える値を上から下の順番で返しましょう。

例

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