LeetCode 108. Convert Sorted Array to Binary Search Tree

문제

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

걸린 시간

- 실패

풀이

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return makeBST(nums, 0, nums.size()-1);
    }
    TreeNode* makeBST(vector<int>& nums, int start, int end){
        // 기저 사례
        if(start > end) return nullptr;
        // 재귀 호출
        int mid = (start+end)/2;
        TreeNode* root = new TreeNode(nums[mid], makeBST(nums, start, mid-1), makeBST(nums, mid+1, end));
        return root;
    }
};

오름차순으로 정렬되어 있는 원소들을 균형잡힌 이진 탐색 트리 형태로 바꾸는 문제이다.

AVL 트리를 떠올리며 어렵게 생각했지만, 정답을 보니 원소가 오름차순으로 정렬되어 있다는 점을 이용하면 재귀 구조만을 이용해 쉽게 만들 수 있었다.

잊었던 포인터 개념들

1. 트리 구조를 유지하기 위해서는 데이터를 힙 공간에 저장하여야 한다.
2. 지역변수로 선언할 경우 함수가 종료될 때 스택에 있는 데이터가 소멸된다.
3. c++ 에서 동적할당을 하기 위한 방법 : [포인터형 데이터 타입] [변수명] = new [데이터 타입];