Leetcode.108.Convert Sorted Arra

题目

给定一个递增的数组, 输出一个平衡BST.
可能有多个结果, 输出一种.

Input: [-10,-3,0,5,9]
Output: 
            0
           / \
         -3   9
        /    /
      -10   5

思路

递归, 中间的是根节点, 将数组划分为左右子数组, 每个子数组的中间为根节点, 根节点左右为左右子树.

TreeNode* sortedArrayToBSTRecrution(vector<int> &nums, int left, int right) {
    int index = (left + right) / 2;
    if (index < 0 || index >= nums.size()) return nullptr;
    if (left > right) return nullptr;

    int val = nums[index];
    TreeNode *node = new TreeNode(val);
    node->left = sortedArrayToBSTRecrution(nums, left, index - 1);
    node->right = sortedArrayToBSTRecrution(nums, index + 1, right);
    return node;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBSTRecrution(nums, 0, (int)nums.size());
}

// 给定一个按升序排列的数组, 输出一个左右子树高度均衡的BST
void Leetcode::main_108() {

    vector<int> nums{-10,-3,0,5,9};
    TreeNode *node1 = sortedArrayToBST(nums);
    cout << 1 << endl;
}

总结

找到规律, 转化为数学的公式.