[Binary Tree][Easy] 108. Convert Sorted Array to Binary Search Tree

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

 

 

Q. 오름차순으로 정렬된 array가 주어질 때 이 array로 균형잡힌 binary tree를 구성하라. 

 

Solution. 

  이미 정렬이 되어 있으므로, 어느 지점을 기준으로 해도 작은 쪽 index 방향(left)은 작은값, 큰 index 방향(right)은 큰 값이 오게 된다. 

 다만 최대한 균형잡힌 기준으로 binary tree를 구성해야 하므로, 가운데를 기준으로 계속 partitioning 하며, 트리를 구성한다. 

 

 

    TreeNode* sortedArrayToBST_BT(vector<int>& nums, int left, int right)
    {
        if(left > right) return NULL;

        int mid = left + (right-left) / 2;
        
        // 중앙값으로 node를 만들되, 왼쪽으로는 작은 index 위치
        // 오른쪽으로는 큰 index 위치가 오게 잘라 나간다.
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = sortedArrayToBST_BT(nums, left, mid-1);
        node->right = sortedArrayToBST_BT(nums, mid+1, right);
        return node;
    }

public:
    TreeNode* sortedArrayToBST(vector<int>& nums) 
    {
        return sortedArrayToBST_BT(nums, 0, nums.size()-1);
    }

 

결과.