leetcode: Convert Sorted Array to Binary Search Tree

问题描述：

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

原问题链接：https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

 

问题分析

　　因为这里要求将排序后的数组转换成高度平衡的二叉搜索树，所以这里转换的时候，每次取的元素节点必须要尽量保证它的左右子树的元素个数是一样的。只有这样才能达到一个尽量平衡的结果。于是我们可以每次去数组中给定范围内的中间元素mid，然后从l到mid - 1的元素递归的去构造它的左子树，从mid + 1到r的范围递归的构造它的右子树。

　　按照这个思路，可以很快得到如下的代码：

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int l, int r) {
        if(l > r) return null;
        int mid = l + (r - l) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, l, mid - 1);
        node.right = sortedArrayToBST(nums, mid + 1, r);
        return node;
    }
}