[CodeSignal] traverseTree (Python)

💡문제

https://app.codesignal.com/interview-practice/task/PhNPP45hZGNwpPchi/description

traverseTree | CodeSignal

💡문제 요약 

- 정수 t의 이진 트리가 주어지면 다음의 노드값을 반환해야 한다. 

*이진 트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조 

이진 트리, 출처 : 위키백과

1.첫번째 요소는 루트이다. 

2.다음 요소는 높이 1에 있는 노드값을 가장 왼쪽에서 오른쪽 순서로 정렬한다. 

3.그 이후의 요소는 동일한 방식으로 정렬된 높이 2에 있는 노드의 값이다. 

 

💡풀이 방법 

이진트리의 BFS를 이용해 풀어준다. 

큐를 이용해 구현

 

def solution(t):
    result, queue = [], [t]
    while queue:
    #pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소를 삭제한다
    #pop(0)은 리스트의 첫 번째 데이터를 제거한다 
    #따라서 첫번째 노드를 제거해준다 
        tree = queue.pop(0)
        if not tree:
            continue
        result.append(tree.value)
        queue.append(tree.left)
        queue.append(tree.right)
    return result

 

💡고찰

📄트리와 그래프의 차이점에 대해 공부필요 

     (트리는 사이클을 가지지 않기 때문에, 구현시 이미 방문한 노드(visted)를 기억할 필요가 없다