leetcode-108.Convert Sorted Array to Binary Search Tree

2017-05-26

题目传送门：Convert Sorted Array to Binary Search Tree

题意：有序数组构造平衡二叉搜索树，二叉搜索树定义：左节点的值都比根节点的值小，右节点的值都比根节点的值大。

思路：很明显，有序数组的中间元素一定是这颗搜索树的根节点，然后递归处理左右区间，直到区间不能划分为止，注意处理区间只有两个元素的时候，这样的话是选出一个根节点，左右两个子节点要有一个为null。

其他的没什么问题。
还要注意判断输入数组为空的问题，一开始我没加判断，能正常跑出来，但在leetcode上提交就TLE了，不知道为啥，后来加了一行特判就过了。

java代码：

/**
 * 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.length == 0) return null;
        return dfs(0,nums.length - 1,nums);
    }
    public TreeNode dfs(int l,int r,int nums[]) {
        if( l > r) return null;
        int mid = (l + r) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        if(mid == 0) {
            root.left = null;
            root.right = dfs(mid + 1,r,nums);
        }
        else if(mid == nums.length - 1) {
            root.left = dfs(l,mid - 1,nums);
            root.right = null;
        } else {
            root.left = dfs(l,mid - 1,nums);
            root.right = dfs(mid + 1,r,nums);
        }
        return root;
    }
}