4 분 소요

BFS

문제

문제 링크

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]

Example 2:

Input: root = [1,null,3] Output: [1,3]

Example 3:

Input: root = [] Output: []

Constraints:

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

스스로 고민

  • 이전에 사용했던 방법을 복습하고 while 문으로 다시 구현해보려고 했다.
  • 근데 2개만 들어있을 경우 오른쪽만 반환되어서 문제를 통과하지 못 했다.
  • 예를 들어 [1,2] 만 있을 경우 실제로는 root 가 1 왼쪽에 2가 들어가기 때문에 1만 반환하게 되는데 실제로는 2개 밖에 없으니 1과 2 모두를 리턴해야 되는 상황이다.
  • 임시 방편으로 해당 케이스만 통과하도록 아래와 같이 만들었다
        if root is not None and root.right is None and root.left is not None and root.left.left is None and root.left.right is None:

            return [root.val] + [root.left.val]
  • 하지만 [1,2,3,4] 일 경우에 3번 트리에서 왼쪽으로 4가 들어갈 경우에도 노드가 1개마 있으니 그냥 왼쪽으로 쳐주는 것 같았다.
  • 기존에 사용했던 패턴과는 다르게 노드가 2개인지 1개인지를 추가해야 통과할 수 있다고 생각했다.
class Solution:

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:

        answer = []

        head = root

        while head:

            if head.left is not None and head.right is not None:

                answer.append(head.val)

                head = head.right

            elif head.left is not None and head.right is None:

                answer.append(head.val)

                head = head.left

            elif head.left is None and head.right is not None:

                answer.append(head.val)

                head = head.right

            else:

                answer.append(head.val)

                head = []

        return answer
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.right = TreeNode(4) or root.right.left = TreeNode(4)
  • 로컬에서는 이렇게 문제를 풀었을 때 답이 [1,3,4] 가 잘 나왔는데 리트코드 사이트에서는 여전히 [1.3] 만 나와서 이해가 안갔다.

  • 이해가 가지 않아서 해당 문제의 Discussion 을 확인해봤는데 단순히 오른쪽이 아니라 오른쪽에서 바라봤을 때 보이는 모든 노드의 값을 반환해야되는 거였다 😑

  • 위와 같은 테스트케이스가 나올 경우 어차피 통과를 못 한다.

해결책

  • 수업시간에 배운 BFS 혹은 DFS를 사용해야 해결이 가능해 보였다.
  • 그렇게 생각한 이유는 각 층을 다 찾아보면서 오른쪽에서 가장 먼저 나오는 노드를 찾아야 하기 때문이다.
  • 근데 각 층마다 오른쪽 값을 갖고 와야하니 BFS가 더 잘 맞겠다고 생각했다.
   1
  / \
 2   3
  \   \
   5   4

1이 있는 층에서는 1
위에 처럼 2, 3 이 있는 층에서는 3
5,4 가 있는 층에서는 4
[1,3,4] 이런 식으로 나와야 된다.

의사코드

  • BFS 를 구현하기 위해서는 collections 모듈의 deque를 사용해야 한다.
  • deque는 큐와 스텍의 특징을 모두 갖고 있는게 특징이다.
  • 우선 root 가 빈 값인지 확인하고 빈 값이라면 빈 값을 리턴해주면서 끝내준다.
  • 빈 값이 아니라면 result 의 빈 리스트를 만들어준다.
  • queue 를 선언하고 deque에 root를 넣어준다.
  • while 문을 통해 queue 의 값이 없을 때 까지 실행시켜준다.
  • 각 층을 확인하기 위해서 floor 를 선언해주고 len(queue)를 담아준다. 이렇게 하면 각 층에 있는 queue 의 갯수를 알 수 있다.
  • 각 층에 큐가 있는 갯수 만큼 반복문을 실행시킨다.
  • 현재 층에서 해당 값이 가장 마지막인지 확인한 후 마지막 값이라면 해당 값을 result에 넣어준다.
  • 이렇게 하는 이유는 왼쪽부분을 큐로 뽑고 다음 순으로 오른쪽 부분을 큐로 뽑기 때문에 만약에 왼쪽 오른쪽 둘 다 있을 경우 len(queue)의 값은 2개가 되고 왼쪽이나 오른쪽 하나만 남아 있을 경우는 len(queue) 의 값은 1이 된다.
  • 값이 1이 될 경우 if 문에서 마지막 값이니 result에 담긴다. 이렇게 하면 마지막 층의 값이 오른쪽에 있든 왼쪽에 있든 노드가 하나만 있을 경우 result에 담겨지고 노드가 두 개 일 경우에는 오른쪽이 자동으로 담기게 된다.

구현 코드

from collections import deque
class Solution:
    def getMinimumDifference(self, root):
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            floor = len(queue)
            for i in range(floor):
                node = queue.popleft()
                print(node.val)
                if i == floor - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result
# BST를 만들기 위해 TreeNode 객체를 사용하여 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)

시간 복잡도와 공간 복잡도

  • 시간 복잡도: 코드는 주어진 이진 트리를 BFS 방식으로 탐색한다. 각 노드는 한 번만 방문되므로 시간 복잡도는 O(N) 다. 여기서 N은 이진 트리의 노드 수다.

  • 공간 복잡도: 큐를 사용하여 노드를 저장하므로 공간 복잡도는 큐의 크기에 따라 결정된다. 각 레벨에서 노드 수만큼 큐에 저장되므로 최악의 경우 이진 트리의 마지막 레벨에 있는 모든 노드가 큐에 저장될 수 있다. 따라서 공간 복잡도는 O(2^h)가 된다. 여기서 h는 이진 트리의 높이를 나타낸다.

회고 과정

  • 문제를 풀면서 BFS에 대해서 조금 이해한 것 같다. 문제를 좀 더 풀어봐야 자신감이 생길 것 같다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

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

        def helper(node, level):
            if node is None:
                return
            if level == len(res):
                res.append(node.val)
            helper(node.right, level + 1)
            helper(node.left, level + 1)
        
        helper(root, 0)
        return res
  • deque 사용 없이 문제를 해결한 케이스다.
  • Node가 none이 아니라면 root 노드를 0번으로 시작해서 현재 층에서 마지막 노드인지를 len 함수를 확인해서 node 값을 넣고 그게 아니라면 재귀호출로 문제를 해결한 방식이다.
  • 이렇게 생각을 못 해서 아쉽기도 하지만 deque 를 알게되어서 좋은 점도 있었다.

댓글남기기

참고