题目描述

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

*示例: *

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \ 
       -3   9 
       /   / 
     -10  5

题解

DFS + 二分查找

这道题给的是有序数组, 根据三个深度优先遍历的性质可知, 这是中序遍历的结果, 不过做这道题时用不到这个性质.

要根据有序数组创建二叉搜索树, 那么就尽量把中间的元素作为根节点, 然后把左边数组中的中间元素作为左节点, 右边数组的中间元素作为右节点, 以此往下推, 获得递归算法流程为:

*终止条件: * 数组的长度为0, 无法创建出节点, 返回null
*递归过程: *
1. 根据已知数组将最中间的元素作为根节点
2. 把前半段的数组递归返回值作为左子节点
3. 把后半段的数组递归返回值作为右子节点
*返回值: * 根据当前数组创建的根节点

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0)
        return null;

    TreeNode temp = new TreeNode(nums[nums.length / 2]);
    temp.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, nums.length / 2));
    temp.right = sortedArrayToBST(Arrays.copyOfRange(nums, nums.length / 2 + 1, nums.length));

    return temp;
}