108.将有序数组转换为二叉搜索树

链接：108.将有序数组转换为二叉搜索树
难度：Easy
标签：树、二叉搜索树、数组、分治、二叉树
简介：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

题解 1 - java

• 编辑时间：2020-02-24
• 执行用时：1ms
• 内存消耗：41.3MB
• 编程语言：java
• 解法介绍：递归，每次取中间点为二叉树节点，前后为左子树和右子树。

class Solution {
	public TreeNode sortedArrayToBST(int[] nums) {
		int len = nums.length;
		if (len == 0)
			return null;
		else if (len == 1)
			return new TreeNode(nums[0]);
		int mid = len / 2;
		TreeNode node = new TreeNode(nums[mid]);
		node.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
		node.right = sortedArrayToBST(Arrays.copyOfRange(nums,mid+1,len));
		return node;
	}
}

题解 2 - typescript

• 编辑时间：2020-07-03
• 执行用时：116ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：每次取中点进行左右分离生成节点。

function sortedArrayToBST(nums: number[]): TreeNode | null {
  function getNode(l: number, r: number): TreeNode | null {
    if (l > r) return null;
    else if (l === r) return new TreeNode(nums[l]);
    else {
      const mid = (r + l) >> 1;
      const node = new TreeNode(nums[mid]);
      node.left = getNode(l, mid - 1);
      node.right = getNode(mid + 1, r);
      return node;
    }
  }
  return getNode(0, nums.length - 1);
}

题解 3 - typescript

• 编辑时间：2021-08-07
• 执行用时：96ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：依次取中值插入。

function sortedArrayToBST(nums: number[]): TreeNode | null {
  return build(nums);
  function build(list: number[]): TreeNode | null {
    if (list.length === 0) return null;
    const mid = (0 + list.length - 1) >> 1;
    const node = new TreeNode(list[mid]);
    node.left = build(list.slice(0, mid));
    node.right = build(list.slice(mid + 1));
    return node;
  }
}