[수업]순열을 이진트리로

문제

풀이

재귀적으로 중위순회 형태로 푸는방법과 진짜 트리형태 처럼 저장하는 방식이 있다.

본인은 중위순회 형태로 풀었으며, 교수님께서는 트리형태를 알려주셨다.

중위순회 형태라면?? 아래 방식으로 재귀로 짜면 구현 가능하다.

tree(left)   
data 처리코드..   
tree(right)   

트리처럼 저장하는 방식이라면??

• 깊이는 배열로 따로 기억!! => b배열

• root(=제일 큰 max)를 구하고 재귀적으로 왼쪽, 오른쪽 서브트리를 작성

• 즉, 함수 인수로 (깊이, 왼쪽, 오른쪽)을 주고 처음엔 (0, 1, n) 이 인수가 될것이다.
  • root는 레벨 0인것.
  • 제일 큰 max가 root인것이고, 맨처음엔 입력받은 n값이 젤 큰값으로써 ‘오른쪽’ 인수로 들어간다.
• 이것을 재귀적으로 깊이 +1하면서 트리구성을 해나가는 방식이다.

이부분을 조금 더 설명해보겠다.

• if(x>y) return : 당연히 왼쪽 값보다 오른쪽값이 작으면 종료시점인것.
• for문 내부의 if(a[i]>a[m]) m=i 의 경우 root를 찾는 것이다!
  • 여기서 root를 찾아서 b배열에 깊이(d)를 저장한다!
• 이후 2개의 재귀가 있다.
  • f(d+1, x, m-1) 재귀는? 왼쪽 서브트리를 구성하는 재귀이다.
    • m이 root로 구했으니까 ‘‘오른쪽’‘은 m-1을 넣은것이다.
  • f(d+1, m+1, y) 재귀는? 오른쪽 서브트리를 구성하는 재귀이다.
    • m이 root였으니까 이보다큰 m+1로 ‘왼쪽’ 인수에 넣은 것이다.
  • 또한 이때 깊이 +1 이기 때문에 ‘d+1’을 인수에 넣은 것이다.

문제를 잘 읽어보면 왼쪽, 오른쪽 서브트리를 만드는 조건이 나와있으니 이것을 참고하면 된다.

결론은 위 과정을 거치게 되면 이진트리 형태로 재귀를 접근한 것이며, 깊이를 따로 b배열로 저장했기 때문에
정답을 출력할 수 있다.