JavaScript로 오름차순으로 정렬된 배열을 이진트리로 변환하기
문제분석
이미 오름차순으로 정렬된 배열이 함수의 인자로 들어올 때, 이 배열을 깊이-균형 이진탐색트리로 만들기
깊이-균형 이진 탐색 트리는 다음과 같이 정의된다.
왼쪽과, 오른쪽 자식트리들의 모든 노드의 깊이에서 차이가 1을 초과하지 않는 이진트리. 또한, 이진 탐색 트리가 되기 위해서는 노드의 왼쪽은 작은 값, 오른쪽은 큰 값을 만족해야한다.
돌파구
이번에도 이 문제를 해결하기 위한 핵심은 재귀호출이다. 재귀호출의 핵심은, 내가 처리하지 못 하니까, 아래 자식 노드에게 일을 위임하는 것이다.
이미 정렬된 배열[-10, -3, 0, 5, 9]가 인풋으로 들어올 때를 예를들면, 직관적으로 가운데 있는 놈이 우리가 만들 이진탐색트리의 최상의 노드(root) 가 된다는 것을 알 수 있다. 그리고 0의 왼쪽([-10, -3])은 이진탐색트리에서 0의 왼쪽에 위치할 것이고, 오른쪽([5, 9])은 0의 오른쪽에 위치할 것이다.
sortedArrayToBST 라는 함수는, 배열을 받아서 이진트리를 만들어주는 함수이다. 그럼 이렇게 해보면 어떨까?
- 가운데를 기준으로 왼쪽 배열을 sortedArrayToBST 함수에 넘겨주어서 만들어진 트리의 주소를 연결한다.
- 가운데를 기준으로 오른쪽 배열을 sortedArrayToBST 함수에 넘겨주어서 만들어진 트리의 주소를 연결한다.
구현
- 재귀 호출이 끝나는 조건 : 들어온 배열이 null 이거나, length 가 0 이면, null 을 리턴한다.
- 먼저, 들어온 배열의 가운데 인덱스를 구한다. : 이미 정렬된 배열이므로, 가운데를 부모노드로 선언한다.
- 가운데를 기준으로 왼쪽 배열에 대해서 이진탐색트리를 만드는 이 함수를 호출한다.
- 가운데를 기준으로 오른쪽 배열에 대해서 이진탐색트리를 만드는 이 함수를 호출한다.
- 리턴 : 만들어진 트리를 리턴한다.
이런식으로 구현하면, DFS 알고리즘 처럼 null 을 만날 때 까지 계속해서 같은 함수를 호출하고, 밑에서 부터 위로 트리가 만들어진다. 즉, 가장 최상위에 있는 노드의 자식들은 재귀 콜스택에서 맨 마지막에 줄줄이 달린 사탕처럼 트리가 리턴되고 그 때, 연결된다.
DFS 알고리즘을 사용하면, 실제 트리가 생성 될 때에는 가장 하단부터 위로 연결된다는 점이 포인트!
