[leetcode][1008] Construct Binary Search Tree from Preorder Traversal
문제 : https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/ 이진 탐색 트리를 전위순회한 결과 배열을 입력값으로 받을 때, 이진 탐색트리를 구한 뒤 루트를 반환하라. 이진탐색트리는 왼쪽 자식 서브트리들의 노드는 루트 노드보다 작고, 오른쪽 자식 서브트리들의 노드들은 루트 노드보다 크다. 이를 이용해서 왼쪽 자식들과 오른쪽 자식들을 구분할 수 있다. 예를 들어, [8,5,1,7,10,12] 일때. 전위 순회이므로 8은 루트가 된다. 8 이후의 배열들 중 8보다 작은 값들은 [5, 1, 7] 이고 8보다 큰 값들은 [10, 12] 이다. 전위 순회이므로 나눈 배열들 중 가장 앞에 있는 요소가 루트의 왼쪽, 오른..
2020. 4. 20.
[leetcode][33] Search in Rotated Sorted Array
문제 : https://leetcode.com/problems/search-in-rotated-sorted-array/ 오름차순으로 정렬된 중복되지 않은 요소들을 가진 배열이 있다. 이 배열을 어떤 인덱스에서 회전시킨다. 예를 들어, [0, 1, 2, 3, 4,5,6,7]은 [4, 5, 6, 7, 0, 1, 2, 3] 가 될 수도 있다. 회전된 배열이 주어질 때, 이 배열에서 target 값이 어디있는지 인덱스를 찾아라. 없다면 -1을 반환. 단, 시간복잡도는 O(logN) 이어야 한다. 이분 탐색으로 풀었다. 배열 [4 5 6 7 8 0 1] [5 1 2 3 4]로 예를 들어보자. 중간 인덱스를 기준으로 왼쪽과 오른쪽이 있고 이들이 오름차순인지 내림차순인지 구한다. 이 때, 오름차순과 내림차순은 배열을..
2020. 4. 19.