两道有挑战的问题（算法村第九关黄金挑战）

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

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解

构造一棵二叉搜索树时，升序序列中的任一个元素都可以作为根节点，然后以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树。

本题要求高度平衡，因此需要选择升序序列的中间元素作为根节点，这本质上就是二分查找的过程。

public TreeNode sortedArrayToBST(int[] nums)
{
    //调用DFS函数，将数组转换为二叉搜索树
    return DFS(nums, 0, nums.length - 1);
}

//深度优先搜索，将数组转换为二叉搜索树
public TreeNode DFS(int[] nums, int left, int right)
{
    //如果左边界大于右边界，则返回null
    if (left > right)
        return null;

    //计算中间位置。若中间结点有两个，则取左边那个
    int mid = left + (right - left >> 1);

    //每次都以中间位置作为根节点
    TreeNode root = new TreeNode(nums[mid]);
    //递归创建左子树
    root.left = DFS(nums, left, mid - 1);
    //递归创建右子树
    root.right = DFS(nums, mid + 1, right);

    return root;
}