LeetCode [ 199 | Python ] Binary Tree Right Side View
업데이트:
문제
주어진 트리를 오른쪽에서 바라보자 !
트리를 오른쪽에서 바라봤을 때 보이는 노드들을 위에서부터 순서대로 반환해야하는 문제.
풀이
주어진 입력인 트리는 불균형한 트리일 가능성이 크다.
따라서 가장 오른쪽의 노드들 뿐만이 아니라 왼쪽으로 삐져나온 트리들도 볼 수 있다.
이점을 생각했을 때 오른쪽부터 노드를 확인해야한다.
또한 오른쪽 노드를 가장 먼저 확인하기 때문에 전위 순회를 택했다.
(hist에 추가할 노드의 우선순위는 가장 오른쪽에 있는 노드이기 때문)
root가None인 경우를 제외하기 위해 이를 확인한다.- 결과를 담을 배열
hist에 해당 노드를 탐색했을 때의 깊이를 알기위한depth를 같이 저장한다. - 전위 순회이므로 가장 먼저 현재 노드를 판단한다.
hist의 가장 마지막에 들어있는 노드의 깊이가 현재 깊이보다 낮은 경우 현재 노드와 깊이를 추가한다.
- 오른쪽 노드에 대해 dfs를 수행한다.
- 왼쪽 노드에 대해 dfs를 수행한다.
- 3 ~ 5의 과정을 재귀적으로 수행한다.
- 얻어낸 결과 리스트를 반환한다.
시도 1
실행시간 : 15ms
메모리 : 13.3MB
class Solution(object):
def rightSideView(self, root):
if root != None :
hist = [[root.val , 0]]
def dfs(start, depth = 0):
if start == None:
return
if hist[-1][1] < depth:
hist.append([start.val, depth])
depth += 1
dfs(start.right, depth)
dfs(start.left, depth)
dfs(root)
return list(map(lambda x : x[0], hist))
return []
개선 1
실행시간 : 17ms
메모리 : 13.3MB
이전에 트리에 대해 살펴 보았을 때 DFS보다는 BFS가 적절하다는 생각을 했다.
(링크에서 적진 않았지만 BFS는 계층적으로 순회할 때 유리하다.)
따라서 너비 우선 탐색으로 또한 구현해 보았다.
위 로직과 처음 None을 확인하는 것 외로는 완전히 같지만, 확실히 깊이를 하나씩 확인해 나아가는 너비 우선탐색이 생각하기 편했다.
하지만 실행시간은 완전히 차이가 없다 라고 말할 수준의 차이를 보였다.
사실 확연한 성능을 확인할 수 없는 이유는 1000 개 정도의 적은 입력 때문이겠지만, 성능 차를 눈으로 확인할 수 없는 것은 확실히 아쉬운 점이었다.
from collections import deque
class Solution(object):
def rightSideView(self, root):
depth = 0
hist = []
def bfs(start):
q = deque()
if start != None:
hist.append([start, depth])
q.append([start, depth])
while q:
x, d = q.popleft()
if x.right != None:
q.append([x.right, d + 1])
if x.left != None:
q.append([x.left, d + 1])
if d > hist[-1][1]:
hist.append([x, d])
bfs(root)
return list(map(lambda x : x[0].val, hist))
생각 & 정리
아쉬운 마음에 간략하고 투박하게 나마 실험해보기로했다.
이렇게
from collections import deque
import time
import sys
sys.setrecursionlimit(10**9)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_binary_tree(num_nodes):
root = TreeNode(1)
current_node = root
for i in range(2, num_nodes + 1):
new_node = TreeNode(i)
if current_node.left is None:
current_node.left = new_node
else:
current_node.right = new_node
current_node = current_node.left
return root
num_nodes = 18000
root = create_binary_tree(num_nodes)
dpast = time.time()
def rightSideView(root):
depth = 0
hist = []
def bfs(start):
q = deque()
if start != None:
hist.append([start, depth])
q.append([start, depth])
while q:
x, d = q.popleft()
if x.right != None:
q.append([x.right, d + 1])
if x.left != None:
q.append([x.left, d + 1])
if d > hist[-1][1]:
hist.append([x, d])
bfs(root)
return list(map(lambda x: x[0].val, hist))
rightSideView(root)
print(f"bfs 결과 -> {time.time() - dpast}")
past = time.time()
def rightSideView(root):
if root != None:
hist = [[root.val, 0]]
def dfs(start, depth=0):
if start == None:
return
if hist[-1][1] < depth:
hist.append([start.val, depth])
depth += 1
dfs(start.right, depth)
dfs(start.left, depth)
dfs(root)
return list(map(lambda x: x[0], hist))
return []
rightSideView(root)
print(f"dfs 결과 -> {time.time() - past}")
결과는 다음과 같았다.
노드 갯수 : 1000
bfs 결과 -> 0.00039505958557128906
dfs 결과 -> 0.0004353523254394531
---------------------------------
노드 갯수 : 5000
bfs 결과 -> 0.0013880729675292969
dfs 결과 -> 0.001750946044921875
---------------------------------
노드 갯수 : 10000
bfs 결과 -> 0.0033609867095947266
dfs 결과 -> 0.004140138626098633
---------------------------------
노드 갯수 : 20000
bfs 결과 -> 0.0058476924896240234
dfs 결과 -> 0.007363080978393555
입력이 커지면 커질수록 두 순회방법에 따른 시간 차이가 점점 커졌다. 20000개도 여전히 작은 입력이지만,
10만개 하면 터진다
결과는 항상 같았다.
순회방법만 적절히 선택해도 큰차이가 벌어질 수 있다는 것을 새삼 크게 깨달았다.
댓글남기기