199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/

Binary Tree Right Side View - LeetCode

Solution

# 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]:
        if not root:
            return []
        ans = []
        layer = [root]
        while(layer):
            ans.append(layer[0].val)
            temp = []
            for node in layer:
                if node.right : temp.append(node.right)
                if node.left : temp.append(node.left)
            layer = temp
        return ans

• 반복문을 사용하여 풀었다.
• 각 층의 모든 노드를 layer에 저장하고, 오른쪽부터 왼쪽 순서대로 저장하여 가장 오른쪽의 val을 접근할 수 있도록 한다.
• temp를 두어서 layer를 계속 쌓지 않고 이전 layer에 덮어 씌워서 메모리를 절약하였다.

Another 1

def rightSideView(self, root):
    if not root:
        return []
    right = self.rightSideView(root.right)
    left = self.rightSideView(root.left)
    return [root.val] + right + left[len(right):]

• 재귀를 이요하여 풀었다.
• 오른쪽과 왼쪽의 값을 불러와서 이어 붙인다.
• 왼쪽의 값은 right의 길이만큼 건너뛰도록 하여 한 층에 하나의 값만 나오도록 한다.
• string 을 붙이는 '+' 연산이 O(n) 만큼 더 걸린다고 한다.

Another 2

def rightSideView(self, root):
    def collect(node, depth):
        if node:
            if depth == len(view):
                view.append(node.val)
            collect(node.right, depth+1)
            collect(node.left, depth+1)
    view = []
    collect(root, 0)
    return view

• DFS 방법으로 함수를 사용한다.
• 오른쪽을 먼저 살펴보고 처음 간 depth에서 값을 저장한다.