## [Leetcode]108. Convert Sorted Array to Binary Search Tree (C++)

### 题目描述

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

### 例子

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST

### 解题思路

``````/**
* 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) {}
* };
*/
#include <vector>

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

private:
TreeNode* buildTree(std::vector<int>& nums, int begin, int end) {
if (begin > end) {
return nullptr;
}

int mid = (begin + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, begin, mid - 1);
root->right = buildTree(nums, mid + 1, end);
return root;
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(n) – n 个节点作为新的二叉搜索树

GitHub 代码同步地址： 108.ConvertSortedArrayToBinarySearchTree.cpp

Built with Hugo
Theme Stack designed by Jimmy