[leetcode][988] Smallest String Starting From Leaf

문제 : https://leetcode.com/problems/smallest-string-starting-from-leaf/

---

DFS로 완전탐색해서 풀었다.

루트를 기준으로 자식 노드로 탐색하면서 문자열을 만들어간다.

현재 노드의 val를 이때까지 만든 문자열 앞에 붙인다.

그리고 리프 노드가 되면 이때까지 만든 문자열을 이때까지 구한 정답 문자열과 비교해서 사전순으로 앞서있다면 정답을 갱신한다.

시간복잡도는 모든 노드를 탐색해야 하므로 O(N + 정답문자열 비교 시간 * 리프노드 개수) 이다.

완전이진트리라 했을 때 정답문자열 비교 시간 * 리프노드 개수는 트리의 높이는 logN이므로 정답 문자열 비교 시간은 logN이고 리프노드 개수는 N/2이므로 N*logN/2가 된다.

좀 더 상세하게 따지면 몇가지 케이스를 따져봐야 하지만 이정도로만 알아보자.. 

---

소스코드 : https://gist.github.com/fpdjsns/683cfcabfa8db69e469f9f35be5e4a33

참고 : [stackoverflow] O(n^2) vs O(n(logN)^2)