트리의 right side view를 얻기 위해서는, 각 level에서 가장 오른쪽에 위치하는 node를 찾아야 한다.
이를 위해 level 단위로 BFS를 수행하면서, 각 level에서 가장 오른쪽(마지막)에 담기는 node의 val을 결과 배열에 담는다.
Idea 2: DFS 💡
DFS를 통해 right child를 우선적으로 방문하면서, 각 호출에서 현재 depth 값과 결과 배열 res의 길이가 동일할 때에만 현재 node의 val을 결과 배열에 담는다.
def dfs(node, depth):
if not node:
return
# 현재까지 모은 res의 길이가 depth의 길이와 같아야, 현재 depth에서 가장 먼저 발견된 node라는 의미
if len(res) == depth:
res.append(node.val)
# right child 부터 우선으로 탐색
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
이 조건으로 현재 보고있는 node가 현재 depth에서 가장 먼저 발견된, 즉 가장 오른쪽에 위치하는 node 라는 것을 보장한다.
Approach
Idea 1: BFS (by level)
트리의 right side view를 얻기 위해서는, 각 level에서 가장 오른쪽에 위치하는 node를 찾아야 한다.
이를 위해 level 단위로 BFS를 수행하면서, 각 level에서 가장 오른쪽(마지막)에 담기는 node의
val을 결과 배열에 담는다.Idea 2: DFS 💡
DFS를 통해 right child를 우선적으로 방문하면서, 각 호출에서 현재
depth값과 결과 배열res의 길이가 동일할 때에만 현재 node의val을 결과 배열에 담는다.이 조건으로 현재 보고있는 node가 현재 depth에서 가장 먼저 발견된, 즉 가장 오른쪽에 위치하는 node 라는 것을 보장한다.
Complexity
O(n)(모든 노드 한 번씩 방문)O(n)/ (DFS)O(h)(recursion stack = height of tree)