[Leetcode/파이썬] 199. Binary Tree Right Side View

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]

Explanation:

Example 2:

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Explanation:

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

 

# 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]:
        q = deque()
        q.append(root)
        res = []

        while q :
            node = None

            for _ in range(len(q)) :
                curr = q.popleft()
                if curr :
                    node = curr		# curr.val 하게 되면 0 값이 들어왔을 때 아래에서 오류 발생
                    q.append(curr.left)
                    q.append(curr.right)

            if node :	# 값 0 은 False로 인식하기 때문에 오류 발생할 수 있다.
                res.append(node.val)

        return res

각 레벨의 가장 오른쪽 노드를 찾아라 인데... 가장 먼저 생각 난 것은 while문 안에 있는 저 for문 이다. 저렇게 하면 각 레벨마다 매듭을 지을 수 있어서 안정적으로 레벨별 분류가 가능해진다.

그럼 가장 오른쪽에 있는 노드들을 찾는 것인데, 이것은 오른쪽에 있는 노드들을 가장 마지막으로 갱신하면 자연스레 가장 오른쪽에 있는 노드가 값에 저장되고 이를 res 리스트에 저장, 반환하면 되는 것이다. 

여기서 주의할 점이라면 if curr : 에서 node를 노드로 갱신해야지 node.val 값으로 변환하면 오류가 날 수 있다. 그래서 반드시 위에는 node 를 TreeNode 값으로 갱신하고 res 리스트에 추가할 때는 val 값으로 추가하자. 

구조가 아주 어려운 코드는 아니니까 한번씩 살펴보면 쉽게 해결할 수 있는 문제라고 생각한다.