BST4 [Leetcode] 538. Convert BST to Greater Tree 문제 : https://leetcode.com/problems/convert-bst-to-greater-tree/ 이진 검색 트리(BST)가 입력으로 주어지면 BST의 모든 키가 원래 키보다 큰 모든 키의 합으로 변경하라. BST를 오른쪽 자식 노드 -> root 노드 -> 왼쪽 자식 노드 순으로 탐색하며 탐색한 노드들의 합을 저장하고 root 노드를 노드의 합으로 갱신하라. 오른쪽 자식 노드 탐색 합 갱신 root->val을 합으로 갱신 왼쪽 자식 노드 탐색 시간복잡도는 O(노드수) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/538.%20Convert%20BST%20to%20Greater%20Tree.cpp 2022. 4. 16. [Leetcode] 1305. All Elements in Two Binary Search Trees 문제 : https://leetcode.com/problems/all-elements-in-two-binary-search-trees/ 두 개의 bst 트리의 루트 노드들이 입력으로 주어질 때, 두 개의 트리들이 가지는 요소들의 오름차순 정렬된 리스트를 구해라. 중위순회 로 두 개의 bst를 각각 탐색하여 정렬된 2개의 리스트를 만든다. 두 개의 리스트를 앞에서부터 탐색하면서 탐색 중인 요소들 중 작은 값을 먼저 정답 배열에 추가하는 식으로 정답 배열을 만들어나간다. 시간복잡도는 두 개의 bst의 노드 개수를 각각 N, M 이라 한다면 O(N + M). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1305.%20All%2.. 2022. 1. 26. [leetcode] 108. Convert Sorted Array to Binary Search Tree 문제 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ 오름차순 정렬된 nums 배열이 주어질 때, height-balanced BST로 변형하라. height-balanced BST는 모든 노드들의 두 하위 트리깊이가 1이상 차이가 나지 않는 이진 트리이다. height-balanced BST가 뭔가 했더니 이런식으로 불균형적인 트리를 만들지말란 의미였다. [그림 1]에서 왼쪽 하위트리의 높이는 1, 오른쪽 하위트리의 높이는 3 이므로 1 이상 차이가 나서 높이 균형 BST가 아니다. 결국 노드들을 왼쪽 오른쪽 균등하게 분배하면서 bst를 만들라는 뜻이다. 정렬된 nums 배열의 중간 값을 현재 노드로 만들고 중간 값.. 2021. 7. 27. [leetcode][701] Insert into a Binary Search Tree 문제 : leetcode.com/problems/insert-into-a-binary-search-tree/ 이진검색트리의 root 노드가 주어질 때 이진검색트리 조건을 만족하며 val 값을 넣어라. val 값은 이진검색트리에 없다고 가정한다. 이진검색트리 규칙대로 루트 노드부터 자식 노드들을 탐색하면서 val보다 탐색중인 노드 값이 작은 경우 오른쪽 자식, 큰 경우 왼쪽 자식으로 탐색해간다. 탐색중에 NULL인 자리를 만나면 val 값을 가지는 노드를 생성하여 트리에 연결한다. 시간복잡도는 O(logN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/701.%20Insert%20into%20a%20Binary%20Search%20Tr.. 2020. 10. 6. 이전 1 다음
