https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
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.
Example:
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: 0 / -3 9 / / -10 5
代码:
/** * 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 { TreeNode * BuildTree(vector<int> &nums, int start, int end) { if(start >= end) return NULL; int mid = (start + end)/2; TreeNode * cur = new TreeNode(nums[mid]); cur ->left = BuildTree(nums, start, mid); cur ->right = BuildTree(nums, mid + 1, end); return cur; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { int n = nums.size(); return BuildTree(nums, 0, n); } };
不是很明白为什么是这么写的 本来想的是写一个 $insert$ 函数然后跑 $nums$ 数组但是没写出来 肥去之后再想吧 指针指来指去不是很搞得清