LeetCode108.-将有序数组转换为二叉搜索树
目录
LeetCode——108. 将有序数组转换为二叉搜索树
1.问题描述
2.解决办法
二分法+递归
- 首先数组是有序的，二叉搜索树也是有序的
- 先找到数组的中间树mid，将他作为根节点
- 他的左子树只能实在left——mid中产生，进行递归即可
- 他的右子树只能实在mid——right中产生，进行递归即可
3.代码实现
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums, 0, nums.length);
}
public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
if (left >= right) {
return null;
}
if (right - left == 1) {
return new TreeNode(nums[left]);
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums, left, mid);
root.right = sortedArrayToBST(nums, mid + 1, right);
return root;
}
}