199. Binary Tree Right Side View

[zeikar]

Problem link

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

Problem Summary

이진 트리가 주어질 때 오른쪽에서 볼 때 보이는 노드들을 출력하는 문제.

Solution

DFS로 조금 지저분하게 풀었는데 BFS가 더 깔끔할거 같긴 하다.
DFS는 오른쪽 노드로 간 경로와 왼쪽 노드로 간 경로를 비교한 다음 오른쪽에서 본 것처럼 덮어 씌우는 방식으로 구현하였다. (문제 설명 그대로 오른쪽에서 보는 방식이다. 이런 문제 풀때 그닥 좋지는 않지만 직관적인 방법)
BFS는 레벨별로 큐에 집어넣은 다음 큐의 가장 오른쪽 노드만 뽑는 방식이다. 이게 코드도 더 깔끔함.

다른 사용자 풀이 보니 postorder로도 풀었는데 이것도 깔끔하다.

Source Code

DFS

# Definition for a binary tree node.
from typing import Optional, List


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]:
        return self.getRightNode(root)

    def getRightNode(self, node: TreeNode) -> List[int]:
        if not node:
            return []

        res = [node.val]

        right = self.getRightNode(node.right)
        left = self.getRightNode(node.left)

        if len(right) < len(left):
            left[0:len(right)] = right
            res.extend(left)
        else:
            res.extend(right)

        return res

BFS

# Definition for a binary tree node.
from typing import Optional, List


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 []
        queue = [root]
        result = []
        while queue:
            result.append(queue[-1].val)
            new_queue = []
            for node in queue:
                if node.left:
                    new_queue.append(node.left)
                if node.right:
                    new_queue.append(node.right)
            queue = new_queue
        return result