199. Binary Tree Right Side View (Tree, Depth-First Search, Breadth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/binary-tree-right-side-view/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 DFS와 BFS 두가지로 풀 수 있다. 두가지 모두 Time complexity가 O(N)이므로 둘 다 살펴보겠다.

1) Recursive DFS

알고리즘은 간단하다. DFS함수는 현재 노드와 현재 노드가 있는 depth를 가지고 있어야한다. 따라서 depth에 따라 ans에 답을 넣을지 말지 알 수 있기 때문이다.

# 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]:
        ans = []
        def dfs(node, depth):
            if not node:
                return

            if len(ans) == depth:
                ans.append(node.val)

            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return ans

Time Complexity: O(n) 각 노드를 방문하므로 노드 개수인 n만큼 시간이 소요된다.

Space Complexity: O(H) 여기서 H는 트리의 Height이다. 따라서 만약 트리가 한쪽으로만 쭉 이어져 있는 worst case 상태라면 O(n)이 되기도 한다.

2) BFS

BFS에서 가장 오른쪽에 있는 노드를 알려면 각 level에서 queue에서 가지고 있는 node들만 가져와야 한다. 따라서 그걸 len(queue)로 가져오고 for문을 통해 가장 오른쪽에 있는 node.val 만 ans에 append하도록 했다.

# 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]:
        ans = []
        if not root:
            return ans

        queue = deque()
        queue.append(root)

        while queue:
            num_nodes = len(queue)

            for i in range(num_nodes):
                node = queue.popleft()
                if i == num_nodes - 1:
                    ans.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return ans

Time Complexity: O(n) 모든 노드들을 돌기 때문에 노드 개수인 n만큼 시간이 소요된다.

Space Complexity: O(d) 여기서 d는 tree에 diameter이다.