将有序数组转化为二叉搜索树. 题目即是题意. 只要输出一个有效的 BST 即可. 此题可以跟 109 题一起做, 要求很接近但是做法不太一样. 例子,
- Example:
- Given the sorted linked list: [-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
这个题可以用递归做. 因为是 BST 的关系, 而且 input 是有序数组, 所以找到数组的 mid 元素, 即是找到了 BST 的根节点. 代码如下
时间 O(n)
空间 O(n)
- /**
- * @param {number[]} nums
- * @return {TreeNode}
- */
- var sortedArrayToBST = function (nums) {
- if (!nums) return null;
- return helper(nums, 0, nums.length - 1);
- }
- var helper = function (nums, low, high) {
- if (low> high) return null;
- var mid = Math.floor((high + low) / 2);
- var node = new TreeNode(nums[mid]);
- node.left = helper(nums, low, mid - 1);
- node.right = helper(nums, mid + 1, high);
- return node;
- }
- [LeetCode] 108. Convert Sorted Array to Binary Search Tree
来源: http://www.bubuko.com/infodetail-3415603.html