199. Binary Tree Right Side View

199. Binary Tree Right Side View

 

# 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 root, null 을 반환하면 안되고, []을 반환해야함
            return [] 

        res = []
        que = deque([root])

        while que: 
            level_size = len(que) 
            for i in range(level_size):
                node = que.popleft()
                # 마지막 노드이면, 제일 오른쪽 노드일테니, res에 추가
                # if i == len(que)-1: 여기에서 len(que) 을 하면, 
                # 계속 바뀌는 길이가 되어서, 제대로 동작하지 않음, 
                # for 밖에서 마지막 개수 제대로 변수로 세팅해야함
                # level_size = len(que) 
                if i == (level_size - 1):
                    res.append(node.val)
                
                # 자식들 왼쪽, 오른쪽 순서대로 큐에 추가
                if node.left:
                    que.append(node.left)

                if node.right:
                    que.append(node.right)

        return res

 

https://youtu.be/ptlVOdWs44Q?si=WQfRxlmDVQritbXT

 

https://youtu.be/JL6eCO5HP_E?si=Id9eiuLVmIwXoni3

 

https://youtu.be/d4zLyf32e3I?si=7wZQYK2t8rNH-ftI

 

3번째 내 코드

# 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]:
    	"""
        # 넓이 우선탐색인 BFS 로 풀어야..
        # BFS는 큐로..
        
        # 트리가 비어 있으면 빈 리스트 반환
        """
        if not root:
            return []

        res = []
        q = deque([root])

        while (q):
            val = None
            for i in range(len(q)):
                node = q.popleft()

                # 왼쪽, 오른쪽 넣었으니. 큐니깐. 오른쪽이 늦게 나올것임
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

                # 계속 값을 넣으니, 오른쪽 값이 최종 업데이트 될것임, 
                # 오른쪽 없으면, 왼쪽 값이..
                val = node.val 
                
            if val != None:
                res.append(val)
        
        return res

 

최종 코드

# 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 []

        res = []
        q = deque([root])

        while q:
            level = 0
            sub = []
            for i in range(len(q)):
                n = q.popleft()
                sub.append(n.val)

                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
            res.append(sub[-1])
            level +=1
        return res