Question
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.
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
# 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]:보기 코드의 트리 구조의 루트 노드 root가 주어집니다.
트리를 구조화한 모습을 오른쪽에서 바라볼 때 보이는 값들을 루트노드 위치부터 순서대로 리스트로 반환하는 문제입니다.
제가 생각한 코드는 다음과 같습니다.
# 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]:
if root == None:
return []
check_depth = 0
stack = [(root,0)]
val_list = []
while stack:
node,now_depth = stack.pop()
if now_depth == check_depth:
val_list.append(node.val)
check_depth+=1
if node.left:
stack.append((node.left,now_depth+1))
if node.right:
stack.append((node.right,now_depth+1))
return val_liststack: 노드를 순회하기 위해 노드를 저장하는 리스트입니다. 노드와 깊이 튜플을 원소로 가집니다.(루트노트,0)으로 초기화합니다check_depth: 탐색해야 하는 노드의 깊이 정수값입니다.val_list: 반환할 값 리스트입니다.- 스택을 통한 깊이탐색을 합니다.
- 스택에서 값에서 노드와 노드의 깊이를 가져옵니다.
- 깊이 탐색중인 깊이가 맞다면
val_list에 저장 후 깊이를1만큼 증가시킵니다. - 서브 노드들을 스택에 추가합니다.
- 문제 조건상 오른쪽의 값이 먼저 보이게 되므로 스택 특성에 맞게 왼쪽노드를 저장 후 오른쪽 노드를 저장합니다.
깊이 탐색을 하며 오른쪽 노드를 우선으로 해서 값이 chack_depth의 깊이에서 값이 등장할 때 마다 저장하는 방식입니다.
if문만 반복된 이유는 조건들 간에 의존관계가 없기 때문입니다.
특정 깊이의 값을 구했다고 다른 노드의 서브트리를 구하지 않으면 다음 층에서 문제가 생깁니다. 그래서 모든 노드를 탐색하며 가야하므로 if문을 반복해서 사용합니다.
그리고 깊이가 어디서 얼마큼 나타날지 모르기 때문에 전체를 순회하는 방식을 고려해야 하는 점도 있습니다.
모두 순회하면서 오른쪽 값을 표현하는데서 어떤 방식을 사용해야할지 고려해본 문제였습니다.
공부!