Leetcode - 108. Convert Sorted Array to Binary Search Tree

문제

정렬된 배열이 주어진다. 이것을 height balanced 이진탐색 트리로 변환하라.

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

해결

배열이 정렬된점 때문에 재귀함수 내에서 root-val 값을 항상 left/right 인덱스의 중앙값으로 하면 된다. 재귀형태의 tree traversal은 두가지 형태가 있는듯. 여러 Tree 문제 유형 확인하기 -> Leetcode - Tree & DFS 문제 (13)

• 1. 트리를 새로 생성하는 경우

Tree *add_node() {
   root->left = add_node();
   root->right = add_node();
   return root;

• 2. 이미 만들어진 트리를 탐색하는 경우

void dfs(root) {
   dfs(root->left);
   dfs(root->right);

반드시 기억하자.. 트리 문제를 몇개를 풀었는데 아직도 첨 보면 햇갈림.

class Solution {
private:
    vector<int> gnums; 
    TreeNode *gen_tree(int left, int right) {
        if (left > right)
            return NULL;
        int mid = (left + right ) / 2;
        TreeNode *root = new TreeNode;
        root->val = gnums[mid];
        root->left = gen_tree(left, mid - 1);
        root->right = gen_tree(mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        gnums = nums;
        return gen_tree(0, nums.size() - 1);
    }
};