Leetcode 199. Binary Tree Right Side View with Python

문제

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.

주어진 이진 트리에 대해 각 레벨의 맨 오른쪽 끝에 있는 노드의 값으로만 이루어진 배열을 리턴하시오.

예시

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4] // 오른쪽 끝에 위에서부터 각각 1, 3, 4의 값을 가진 노드가 있다.

제한

• The number of nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

풀이법

1. BFS

이전에 풀었던 문제

https://velog.io/@ilov1112/Leetcode-102.-Binary-Tree-Level-Order-Traversal-with-Python

에서 이미 레벨별 왼쪽부터 오른쪽까지 모든 노드를 저장하는 bfs search를 그대로 사용해

각각의 레벨에서 가장 우측에 있는 값들만 빼내면 된다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class LevelNode:
    def __init__(self, node: TreeNode, level: int):
        self.node = node
        self.level = level

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root == None: return []

        q = [ LevelNode(root, 0) ]

        ans = dict()

        while len(q) != 0:
            node = q[0]
            q.pop(0)
            if node.level not in ans:
                ans[node.level] = list()
            ans[node.level].append(node.node.val)
            if node.node.left != None:
                q.append(LevelNode(node.node.left, node.level + 1))
            if node.node.right != None:
                q.append(LevelNode(node.node.right, node.level + 1))

        ret = []
        for i in range(10000):
        // 최 우측에 있는 값들을 빼서 List에 저장하기.
            if i not in ans: break
            ret.append(ans[i][len(ans[i])-1])

        return ret
        

2. DFS

오른쪽 Node를 먼저 순회하도록 DFS를 구현 한뒤 각각의 level에 따라 첫번째로 순회하는 값만 답에 넣고 리턴한다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def dfs(root: Optional[TreeNode], ans, level: int = 0):
	// 이 레벨을 처음 순회 할 경우 append
    if len(ans) <= level: ans.append(root.val)
    
    // 오른쪽 우선하여 순회		
    if root.right != None:
        dfs(root.right,ans, level + 1)
    if root.left != None:
        dfs(root.left,ans, level + 1)

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        ans = []
        dfs(root, ans)
        return ans

따로 level을 저장할 필요도 없어 BFS보다 빠르고 저장공간도 덜쓴다.