[분할정복, 재귀] LeetCode 108번 문제 학습

 

이 문제는 오름차순으로 정렬된 배열을 높이 균형 이진 탐색 트리(Height-Balanced BST)로 변환하는 거임

 

 

문제 이해

• 입력: 오름차순으로 정렬된 배열 (예: [-10, -3, 0, 5, 9]).
• 출력: 이진 탐색 트리(BST)인데, 높이가 균형을 이루고 있어야 해. BST는 왼쪽 서브트리의 모든 값이 노드보다 작고, 오른쪽 서브트리의 모든 값이 노드보다 큰 트리임
• 높이 균형: 트리의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1이어야 함.

정렬된 배열을 BST로 만들 때, 중간 값을 루트로 선택하면 높이 균형을 유지할 수 있

• 배열이 정렬되어 있으니까 중간 값은 자연스럽게 왼쪽 절반과 오른쪽 절반을 나눠서 시작.
• 왼쪽 절반은 왼쪽 서브트리, 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 만들면 균형이 잡힘.
• 이 방식은 이진 탐색처럼 "분할 정복" 느낌으로 동작함.

예 [-10, -3, 0, 5, 9]

• 중간 값 0을 루트로 선택.
• 왼쪽 배열 [-10, -3] → 왼쪽 서브트리.
• 오른쪽 배열 [5, 9] → 오른쪽 서브트리.
• 각 서브트리에서도 중간 값을 루트로 반복.

---

 

어떻게 풀어야 할까?

• 재귀적 접근:
  • 배열의 중간 인덱스를 찾아 그 값을 루트 노드로 만듦
  • 중간 인덱스 왼쪽 부분으로 왼쪽 서브트리를, 오른쪽 부분으로 오른쪽 서브트리를 재귀적으로 구성.
• 알고리즘 단계:
  • 기본 케이스: 배열이 비었으면(start > end) 널 반환.
  • 중간 값 선택: mid = (start + end) / 2로 중간 인덱스를 구함.
  • 노드 생성: mid 위치의 값을 루트로 설정.
  • 재귀 호출:
    • 왼쪽: start부터 mid-1까지.
    • 오른쪽: mid+1부터 end까지.
• 주의점:
  • 배열 인덱스를 다룰 때 범위를 잘 관리해야 함(오버플로우 방지 등).
  • BST 속성을 유지하려면 정렬된 상태를 그대로 활용하면 됨

---

package main

import "fmt"

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}

	mid := len(nums) / 2

	root := &TreeNode{Val: nums[mid]}

	root.Left = sortedArrayToBST(nums[:mid])
	root.Right = sortedArrayToBST(nums[mid + 1:])

	return root
}

func main() {
	fmt.Println(sortedArrayToBST([]int{1, 2, 3, 4, 5}))
}

 

왼쪽 Node가 작은 값이 이루어지게 Left로 정의하여 해당 함수를 재귀 호출

오른쪽 Node가 왼쪽보다는 큰 값으로 이루어 질 수 있게, Root 중간을 제외한 값을 오른쪽으로 재귀 호출

 

사용하는 알고리즘

• 분할 정복(Divide and Conquer): 배열을 반으로 나누고 각 부분을 재귀적으로 해결하는 방식.
• 재귀: 트리 구조를 만들 때 자연스럽게 사용.

---

감 잡기 위한 예시

배열이 [1, 2, 3, 4, 5]라고 해보자:

1. 중간 값 3을 루트로.
2. 왼쪽 [1, 2] → 중간 값 2가 루트, 1은 왼쪽 자식.
3. 오른쪽 [4, 5] → 중간 값 5가 루트, 4는 왼쪽 자식.

    3
   / \
  2   5
 /   /
1   4