[Leetcode 199] - Binary Tree Right Side View w/ 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.

 

 

이진 트리 우측, 조금 거리가 있는곳에서 바라본다고 생각해보자

우측에서 보이는 노드를 위에서 아래로 배열에 저장해서 리턴

 

 

 

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

 

 

 

---

 

 

 

 

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: []

 

 

 

---

 

 

 

이 문제는 DFS, BFS 둘다 사용해서 풀어 봤다

 

BFS 부터 살펴 보면 deque를 사용해 왼쪽에서 오른쪽까지 확인 하는 방법을 사용했다

(오른쪽부터 확인하는건 DFS에서 풀이 해봤다)

 

 

1. que가 비어 있지 않으면 → 현재 que에 있는 길이 만큼 계속해서 que에서 값을 popleft한다

2. 이를 통해 node가 None이 아니라면 계속해서 right을 최신화 시켜 제일 오른쪽 값을 기억한다

3. 길이가 끝났을때 ans에 저장 → que가 끝나면 ans 리턴

 

class Solution:
    def rightSideView(self, root):
        ans = []
        que = deque([root])

        while que:
            right = None
            length = len(que)

            for _ in range(length):
                node = que.popleft()
                if node:
                    right = node
                    que.append(node.left)
                    que.append(node.right)
            
            if right: ans.append(right.val)
        
        return ans

 

 

운이 좋았던건지 굉장히 빠른 런타임, 좋은 메모리가 나왔다

 

 

 

 

---

 

 

 

DFS 풀이는 미리 Node가 None인지 확인하고 제일 오른쪽만 확인하는 방식을 선택했다

※ 그래도 모든 노드를 확인해야 된다

 

 

1. 오른쪽에서 왼쪽으로 확인

2. 현재 Node가 None이라면 바로 넘어가기

3. 현재 깊이가 ans랑 같다면 (그 깊이에 아직 값을 안 넣었다면) ans에 추가

4. 나머지 깊이에 있는 Node를 재귀를 통해 확인한다

5. ans 리턴

 

class Solution:
    def rightSideView(self, root):
        ans = []
        level = 0

        def dfs(root, level):
            if not root: return
            
            if len(ans) == level:
                ans.append(root.val)
            
            dfs(root.right, level + 1)
            dfs(root.left, level + 1)
        
        dfs(root, level)
        return ans

 

 

비슷한 결과