[Python/DailyAlgo] 94, 95, 96. 트리 전위, 중위, 후위 순회

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

이진 트리의 순회

https://dailyalgo.kr/ko/problems/94

https://dailyalgo.kr/ko/problems/95

https://dailyalgo.kr/ko/problems/96

---

풀이

트리 전위 순회

def solution(childNodes):

    def preorder(node):
        # 종료 조건
        if node == -1:
            return
        # 점화식
        answer.append(node)
        preorder(childNodes[node-1][0])
        preorder(childNodes[node-1][1])

    answer = []
    preorder(1)
    return answer

# 입력 : 이진 트리, 단 1번 노드부터 시작.
# 출력 : 트리 순회 결과를 담은 리스트

트리 중위 순회

def solution(childNodes):

    def inorder(node):
        # 종료 조건
        if node == -1:
            return
        # 점화식
        inorder(childNodes[node-1][0])
        answer.append(node)
        inorder(childNodes[node-1][1])

    answer = []
    inorder(1)
    return answer

# 입력 : 이진 트리, 단 1번 노드부터 시작.
# 출력 : 트리 순회 결과를 담은 리스트

트리 후위 순회

def solution(childNodes):

    def postorder(node):
        # 종료 조건
        if node == -1:
            return
        # 점화식
        postorder(childNodes[node-1][0])
        postorder(childNodes[node-1][1])
        answer.append(node)

    answer = []
    postorder(1)
    return answer

# 입력 : 이진 트리, 단 1번 노드부터 시작.
# 출력 : 트리 순회 결과를 담은 리스트