4.3 깊이의 리스트

문제

이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 

즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야한다. 

 

접근법

재귀를 이용한 전위탐색으로 해결하거나, BFS로 해결이 가능하다. 

두 방법모두 비슷한 탐색법이지만, 재귀를 이용한 전위탐색은 탐색시 logN만크의 추가공간을 요구한다. 

하지만 어쩌피 return할때  무조건 N만큼 공간을 차지하기 때문에 N에 비교하면 logN은 많은 공간이 아니고, 공간 효율성 측면에서는 두 방법모두 O(N)이다. 

 

아래 코드는 BFS로 탐색하여 해결한 코드

def Solution(root):
    level_list = []
    current = []
    if root is not None:
        current.append(root)

    while current :
        level_list.append(current)
        parents = current
        current = []
        for parent in parents:
            if parent.right is not None:
                current.append(parent.right)
            if parent.left is not None:
                current.append(parents.left)

    return level_list