트리 순회(전위 순회, 중위 순회, 후위 순회)

문제 url: X

난이도: 하

정답률:

권장 시간: 30분

권장 시간 복잡도: O(N)

 

---

문제 설명

이진 트리를 표현한 리스트 nodes를 인자로 받습니다. 예를 들어서 nodes가 [1,2,3,4,5,6,7]이면 다음과 같은 트리를 표현한 것입니다. 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution() 함수를 완성해주세요.

제한사항

• 입력 노드 값의 개수는 1개 이상 1,000개 이하이다.
• 노드 값은 정수형이며, 중복되지 않는다

입출력 예

nodes	result
[1,2,3,4,5,6,7]	["1 2 4 5 3 6 7", "4 2 5 1 6 3 7", "4 5 2 6 7 3 1"]

예시 2

numbers = [5,0,2,7]

1. 가능한 모든 두 숫자의 합을 구합니다:
   • 2 = 0 + 2
   • 5 = 5 + 0
   • 7 = 0 + 7, 5 + 2
   • 9 = 2 + 7
   • 12 = 5 + 7
2. 결과적으로 [2,5,7,9,12]를 오름차순으로 반환해야 합니다.

---

내 풀이

# 전위 순회
def preorder(nodes,idx):
  if idx < len(nodes):
    // print("visiting %f",nodes[idx])
    ret = str(nodes[idx])+" "
    ret += preorder(nodes, 2*idx +1)
    ret += preorder(nodes, 2*idx +2)
    return ret

  else:
    // print("done")
    return ""

# 중위 순회
def inorder(nodes,idx):
  if idx < len(nodes):
    // print("passing %f",nodes[idx])
    ret = inorder(nodes, 2* idx + 1)+" "
    ret += str(nodes[idx])
    ret += inorder(nodes, 2*idx +2)
    // print("visiting %f",nodes[idx])
    return ret
  else:
    return ""
    
# 후위 순회
def postorder(nodes, idx):
  if idx < len(nodes):
    // print("passing %f",nodes[idx])
    ret = postorder(nodes, 2* idx + 1)+" "
    ret += postorder(nodes, 2*idx +2)
    ret += str(nodes[idx])
    // print("visiting %f",nodes[idx])
    return ret
  else:
    // print("done")
    return ""
    
def solution(nodes):
  return [preorder(nodes,0)[:-1], inorder(nodes,0)[:-1], postorder(nodes,0)[:-1]]