1130. Minimum Cost Tree From Leaf Values
https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
문제
풀이
바이너리 트리쪽에만 생각하다 보니 도무지 감이 잡히지 않았다. 바이너리 트리를 만들고 어떻게 하는 것이 아니라 왼쪽, 오른쪽 나누어 생각하면 된다.
예를 들어 arr = [6,2,4,7] 일 때
1. (left = [6], right = [2,4,7]), (left = [6,2] right = [4,7]), (left = [6,2,4], right = [7])의 경우의 수로 나타낼 수 있고
2. (left = [6], right = [2,4,7])인 경우 left = [6]만 있으므로 제외하고 right =[2,4,7] 에서 왼쪽 오른쪽 나누어서 생각하면 된다.
3. (left = [2], right = [4,7]), (left = [2,4], right = [7])으로 나누어지고 마찬가지로 (right = [4,7])과 (left = [2,4])를 왼쪽 오른쪽 나누어서 생각하면 된다.
4. (left = [4], right = [7]), (left = [2], right = [4])로 나누어 질 것이다.
5. 즉 DFS를 사용하면 되는데 종료조건에는 배열에 원소가 한 개 일때 즉 left = [4]등 일 때 리턴한다. 해당 조건을 l = r가 같을 때이다.
6. 재귀구조이기 때문에 불필요한 계산이 있을 수 있으니 Cache를 만들어 두고 Cache에 저장된 값이면 그 값을 리턴하여 불필요한 계산을 줄인다.
7. 최소값을 구하는 문제이기에 왼쪽, 오른쪽으로 만들어 질 수 있는 경우의 수에서 최소값을 Cache에 저장한다.
결과
