Convert Sorted Array To Binary Search Tree

problem

정렬된 배열이 주어질 때, 균형 트리를 만드는 문제입니다.
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

solution

/**
 * problem No : 108
 * 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) {
        int size = nums.size();
        return makeBST(nums, 0, size);
    }
    TreeNode* makeBST(vector<int>& nums, int start, int end){
        if(start >= end) return NULL;
        int middle = (start + end)/2;
        TreeNode* curr = new TreeNode(nums[middle]);
        curr->left = makeBST(nums, start, middle);
        curr->right = makeBST(nums, middle+1,end);
        return curr;
    }
};

후기

처음에는 while이나 iter로 만들려고 했다가 막혀서 못 풀다가
재귀로 풀어보니까 쉽게 풀렸다.

배열을 포인터로 안줬더니 복사하느라고 시간이랑 메모리를 엄청 먹었는데
call by reference로 바꿨더니 성능도 좋아졌다.

[0,1,2,3,4,5,6,7,8,9]가 들어오면

• Node 5 made

==========================
left ->[0,5]

• Node 3 made

right->[6,10]

• Node 8 made

==========================
left ->[0,2]

• Node 1 made

right->[3,5]

• Node 4 made

---

left ->[6,8]

• Node 7 made

right->[9,10]

• Node 9 made

==========================
reft->[0,1]

• Node 0 made

right->[2,2]

• return

reft->[3,4]

• Node 3 made

right->[5,5]

• return

reft->[6,7]

• Node 6 made

right->[8,8]

• return

reft->[9,9]

• return

right->[10,10]

• return