199. Binary Tree Right Side View (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.

 

 

 

풀이

 

 

왼쪽 기준으로 아래의 노드들을 리스트에 담아서 출력하라는 줄 알고 '어? 이번엔 좀 쉽겠는데?' 라고 생각했던 나를 반성한다.

 

최초 코드

lass Solution(object):
    def rightSideView(self, root):
        self.result = []
        self.findRight(root)

        return self.result
    def findRight(self, node):
        if node == None:
            return
        self.result.append(node.val)
        if node.right == None:
            self.findRight(node.left)
        self.findRight(node.right)

단순하게 노드의 오른쪽을 탐색하면서 각 값을 리스트에 담아줬다, 만일 오른쪽 노드가 존재하지않고 왼쪽노드만 존재한다면, 왼쪽노드 부터 다시 오른쪽 노드로 탐색하게 만들었다. 하지만... 

오른쪽으로만 탐색한다면 1,3 이맞는데 4가 갑자기..?

 

문제를 잘못이해했다는걸 알았다 ㅋㅋ 어쩐지 문제가 단순하다 했더니.. 문제를 다시 보면 오른쪽 방향에서 트리를 바라볼때  보이는 가장 오른쪽 노드를 리스트에 담아서 보내는 문제이다. 트리의 각 뎁스 기준으로 가장 오른쪽에 있는 값을 반환해주면 되는 문제

 

1.트리기준으로 오른쪽으로 탐색해 내려가며 각 깊이의 레벨별로 첫번째로 나오는 값들을 찾아주면서 리스트에 담으며 

리스트에 담긴 개수와 각 뎁스의 깊이를 기준으로 플래그를 둔다, 

 

2. 각 depth의 레벨의 첫번째로 들어오는 값은 오른쪽에 있는 먼저 탐색이 되므로 list 안에 들어있는 값의 개수와 현재 레벨이 동일하다면 list에 추가시켜준다, (depth 깊이 마다 list에 하나씩 추가하므로 depth의 깊이와 list의 개수는 동일하게됨)

class Solution(object):
    def rightSideView(self, root):
        self.result = [] # return 리스트 
        self.findRight(root,0) # 루트와 뎁스의 깊이 0부터 시작 
        return self.result
    
    def findRight(self, node,level):
        if node == None:
            return
        if len(self.result) == level:  # result의 개수와 depth의 레벨이 같다면 현재값 추가
            self.result.append(node.val) 
        self.findRight(node.right,level+1) # 오른쪽으로 먼저 재귀로 탐색
        self.findRight(node.left,level+1) # 오른쪽 탐색 후 왼쪽 탐색

 

 

다른사람의 풀이

class Solution(object):
    def rightSideView(self, root):
        a=self.bfs(root)
        res=[]
        for i in a:
            res.append(i[-1])
        return res
        
        #BFS TRAVERSAL    
    def bfs(self,root):
            res=[]
            q=collections.deque()
            q.append(root)

            while q:
                level=[]
                len_q=len(q)
                for i in range(len_q):
                    node=q.popleft()
                    if node:
                        level.append(node.val)
                        q.append(node.left)
                        q.append(node.right)
                if level:
                    res.append(level)
            return res

리스트 개수와 깊이를 플래그로 두고 bfs탐색을하며

리스트 개수와 깊이가 동일하다면 값을 추가해주는  방법을 bfs로 구현했다.