파이썬 코딩테스트 스터디 6주차 #2 - 몸풀기 문제 - 트리 순회

트리 순회

 

이진 트리를 표현한 리스트 nodes를 인자로 받는다.

예를 들어 nodes가 [1,2,3,4,5,6,7]이면 다음과 같은 트리를 표현한 것.

 

코딩 테스트 합격자 되기 : 파이썬편 - 289page

해당 이진 트리에 대해 전위 순회, 중위 순회, 후위 순회

결과를 반환하는 solution 함수 구현하기

 

 

제약 조건

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

입출력 예시

nodes	return
[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"]

 

 

결국은 list 자료형으로 구성했고,

다만 idx를 차례대로 순회하는 것이 아닌

각 전위, 중위, 후위 방식대로 순회 

 

근데 왠지 차례대로 찾는 것보다 연산?

if 조건 계산을 더 많이 하는 것 같은 생각이...

def preorder(nodes,idx):
   if idx < len(nodes):
      ret = str(nodes[idx])+" "
      ret += preorder(nodes,idx*2+1)
      ret += preorder(nodes,2*idx+2)
      return ret 
   else :
      return ""
def inorder(nodes,idx):
   if idx < len(nodes):
      ret = inorder(nodes,idx*2+1)
      ret += str(nodes[idx]) +" "
      ret +=  inorder(nodes,2*idx+2)
      return ret
   else :
      return ""
def postorder(nodes,idx):
   if idx < len(nodes):
      ret =  postorder(nodes,idx*2+1)
      ret += postorder(nodes,idx*2+2)
      ret += str(nodes[idx]) + " "
      return ret
   else : 
      return ""

def solution(nodes):
  print( [
      preorder(nodes,0)[:-1],
      inorder(nodes,0)[:-1],
      postorder(nodes,0)[:-1]          
   ])

solution([1,2,3,4,5,6,7])

 

console에 찍기위해 solution함수안에서 print로 변경

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.