題目:

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
將一個排序好的陣列轉成二元樹。

解題思路:

利用二分法找尋每個的根節點，並搭配遞迴將其左右依序找出，直到二分法條件不符合就回傳。

C版本:

struct TreeNode* convert(int* nums,int start,int end)
{
     if(start > end)
          return NULL;
     else{
         int mid = (start+end)/2;
         struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
         node->val = nums[mid];
         node->left = convert(nums,start,mid-1);
         node->right = convert(nums,mid+1,end);
         return node;
     }
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return convert(nums,0,numsSize-1);
}

Javascript版本:

var sortedArrayToBST = function(nums) {
    return traveler(nums, 0, nums.length)
};

var traveler = function(temp, start, end)
{
    if(start >= end)
        return null
    else
    {
        var mid = Math.floor((start+end) / 2);
        var result = new TreeNode(temp[mid]);
        result.left = traveler(temp, start, mid)
        result.right = traveler(temp, mid+1, end)
        return result;
    }    
};

程式Github分享:

https://github.com/SIAOYUCHEN/leetcode

相似主題分享:

https://ithelp.ithome.com.tw/users/20100009/ironman/2500
https://ithelp.ithome.com.tw/users/20113393/ironman/2169
https://ithelp.ithome.com.tw/users/20107480/ironman/2435
https://ithelp.ithome.com.tw/users/20107195/ironman/2382
https://ithelp.ithome.com.tw/users/20119871/ironman/2210
https://ithelp.ithome.com.tw/users/20106426/ironman/2136

本日分享:

Giving up is also a choice. Giving up is not incompetent because you have a better choice. Sometimes, giving up is more courage than persistence.
放棄同樣是一種選擇，放棄並不是自己無能，而是因為自己有了更好的選擇。有時候，放棄比堅持還需要勇氣