leetcode刷題，總結，記錄，備忘 108

leetcode108Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

這個題目使用遞歸和二分即可，一直尋找數組的中點，作為根節點，将數組截為兩半，分别遞歸調用，前一半的結果儲存為左節點，後半結果儲存為右節點，如果數組中隻剩2個數，即第二個大數做根節點，小數為其左節點，若數組中隻有一個數，直接傳回該節點。具體代碼如下。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() >= 3)
        {
            TreeNode * root = new TreeNode(nums[nums.size() / 2]);
            vector<int> l(nums.begin(), nums.begin() + nums.size() / 2);
            vector<int> r(nums.begin() + nums.size() / 2 + 1, nums.end());
            root->left = sortedArrayToBST(l);
            root->right = sortedArrayToBST(r);
            return root;
        }
        else if (nums.size() == 2)
        {
            TreeNode * root = new TreeNode(nums[1]);
            TreeNode * left = new TreeNode(nums[0]);
            root->left = left;
            return root;
        }
        else if (nums.size() == 1)
        {
            TreeNode * root = new TreeNode(nums[0]);
            return root;
        }
    }
};