问题描述
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
解决思路
二分法找中间节点放入数组，递归解决。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//corner case
if(nums == null) return null;
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right){
if(left > right) return null;
if(left == right) return new TreeNode(nums[left]);
int mid = (right + left) / 2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = helper(nums, left, mid - 1);
cur.right = helper(nums, mid + 1, right);
return cur;
}
}
复杂度分析
- 时间复杂度：O(2^n)
- 空间复杂度：O(1)
