LeetCode108 Convert Sorted Array to Binary Search Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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

样例

1

思路

将有序数组转成二叉搜索树。

由于是有序数组,每次在中间位置将数组分成左右两部分递归下去即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 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* build(vector<int>& nums, int l, int r) {
if (l > r) return NULL;
int mid = l + (r - l + 1) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, l, mid - 1);
root->right = build(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
};
分享到 评论