문제 설명
주어진 좌표 정보로 이진 트리를 구성한 후, 전위 순회와 후회 순회 결과를 반환하는 문제
예제 입력/출력
nodeinfo | result |
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] | [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] |
제약 조건
•
◦
모든 노드의 좌표 값
문제 풀이
•
문제 의도
1.
이진 탐색 트리(BST)를 만들 수 있는지?
2.
전위 순회(preorder)의 개념을 알고 있는지?
3.
후위 순회(postorder)의 개념을 알고 있는지?
•
접근1 이진 탐색 트리 초기화
◦
이진 탐색 트리를 구현하기 위해 준비되어야 하는 것은 트리의 노드이다.
◦
노드는 아래의 3개 필드를 가진다.
1.
Data: 노드의 실질적 데이터가 들어가는 필드
2.
Left: 노드의 왼쪽 자식 노드
3.
Right: 노드의 오른쪽 자식 노드
◦
data 필드에는 각 노드의 x좌표, y좌표, 그리고 해당 노드의 고유 인덱스를 저장한다.
◦
이진 탐색 트리를 구성하기 위한 노드를 정의하기 위해 다음과 같이 Node 클래스를 정의했다.
class Node:
def __init__(self, id, x, y):
self.id = id
self.x = x
self.y = y
self.left = None
self.right = None
N = len(nodeinfo)
# 1. 트리 생성
node_list = []
for i in range(N):
node_list.append(Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]))
Python
복사
•
접근2 이진 탐색 트리 삽입
◦
이제 이진 탐색 트리의 삽입 연산 메소드를 통해 트리를 생성할텐데 그 전에 정렬을 한번 해주어야 한다.
▪
문제에서 주어진 조건에 따라, y값이 클수록 상위 레벨에 위치한다.
▪
따라서 y값이 큰 노드부터 차례대로 트리에 삽입해야한다.
◦
정렬을 하는 여러 가지 방법이 있겠지만, __it__ 메서드를 활용하면 객체 간의 비교 연산을 수행할 수 있어 정렬이 더욱 직관적으로 가능하다.
▪
정렬 기준은 먼저 y값을 내림차순하고 y값이 같다면 x값을 오름차순 하도록 해주었다.
class Node:
def __lt__(self, other):
if (self.y == other.y):
return self.x < other.x
return self.y > other.y
node_list.sort()
Python
복사
◦
정렬이 완료되면 삽입 연산 메소드(addNone)를 구현한다.
▪
매개변수로 parent(부모 노드)와 child(삽입할 자식 노드)를 받는다.
▪
현재 노드보다 자식 노드가 x 좌표가 작고, 현재 노드의 왼쪽 자식이 비어있다면 왼쪽으로 삽입한다.
•
이때, 왼쪽 자식이 이미 존재한다면 삽입이 불가능하므로 재귀 호출을 한다.
▪
그 반대라면 오른쪽에 삽입한다.
•
이때, 오른쪽 자식이 이미 존재한다면 삽입이 불가능하므로 재귀 호출을 한다.
def addNode(parent, child):
if child.x < parent.x:
if parent.left is None:
parent.left = child
else:
addNode(parent.left, child)
else:
if parent.right is None:
parent.right = child
else:
addNode(parent.right, child)
Python
복사
◦
node_list는 y값을 내림차순으로 정렬한 노드 리스트이므로 첫 번째 노트가 루트(root)가 된다. 이후 모든 노드를 addNone를 사용해 삽입한다.
root = node_list[0]
for i in range(1, N):
addNode(root, node_list[i])
Python
복사
•
접근3 전위 순회, 후위 순회
◦
전위 순회는 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 노드의 방문 순서를 리스트에 저장하여 반환한다.
def preorder(ans, node):
# Base Case
if node is None:
return
# Recursive Case
ans.append(node.id)
preorder(ans, node.left)
preorder(ans, node.right)
return ans
answer = [[], []]
preorder(answer[0], root)
Python
복사
◦
후위 순회는 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순으로 노드의 방문 순서를 리스트에 저장하여 반환한다.
def postorder(ans, node):
# Base Case
if node is None:
return
# Recursive Case
postorder(ans, node.left)
postorder(ans, node.right)
ans.append(node.id)
return ans
answer = [[], []]
postorder(answer[1], root)
Python
복사
풀이 코드
import sys
sys.setrecursionlimit(10**6)
class Node:
def __init__(self, id, x, y):
self.id = id
self.x = x
self.y = y
self.left = None
self.right = None
def __lt__(self, other):
if (self.y == other.y):
return self.x < other.x
return self.y > other.y
def addNode(parent, child):
if child.x < parent.x:
if parent.left is None:
parent.left = child
else:
addNode(parent.left, child)
else:
if parent.right is None:
parent.right = child
else:
addNode(parent.right, child)
def preorder(ans, node):
# Base Case
if node is None:
return
# Recursive Case
ans.append(node.id)
preorder(ans, node.left)
preorder(ans, node.right)
return ans
def postorder(ans, node):
# Base Case
if node is None:
return
# Recursive Case
postorder(ans, node.left)
postorder(ans, node.right)
ans.append(node.id)
return ans
def solution(nodeinfo):
N = len(nodeinfo)
# 1. 트리 생성
node_list = []
for i in range(N):
node_list.append(Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]))
node_list.sort()
root = node_list[0]
for i in range(1, N):
addNode(root, node_list[i])
# 2. 순회
answer = [[], []]
preorder(answer[0], root)
postorder(answer[1], root)
return answer
Python
복사
