算法学习：leetcode 108. 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

做这题首先要了解一个平衡二叉搜索树是什么样的：

1）了解二叉树

2）了解平衡二叉树

3）了解二叉搜索树

简单来说一个二叉搜索树是任何节点都大于其左子节点，小于其右子节点。

这其实就是一种对数据的排序，左边的都小于右边，我在查找树中取一个节点的值和要查找的目标值比较，目标值大于当前节点，则到当前节点右边继续查找，目标值小于当前节点，则到当前节点左边继续查找。

搜索树的查找，其实就相当于在做二分查找。

二分查找，是基于一个有序数组，每次折半比较，判断是否相等，相等则找到目标值，不相等则判断大于还是小于，来决定向左查找还是向右查找。

代码思路使用了递归，分别递归当前左节点和右节点，直到数组中的元素都处理完。

public static TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0) {
            return null;
        }
        //数组折半
        int middle = nums.length/2;
        TreeNode tn = new TreeNode(nums[middle]);

        //左子树递归
        tn.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,middle));
        //右子树递归
        tn.right = sortedArrayToBST(Arrays.copyOfRange(nums,middle+1,nums.length));
        return tn;
    }

完整代码：

import java.util.Arrays;

/**
 * www.itzhimei.com
 */
public class LC108 {

    public static void main(String[] args) {
        int[] nums = {-10,-3,0,5,9};
        TreeNode treeNode = sortedArrayToBST(nums);
        System.out.println(treeNode.val);
        System.out.println(treeNode.left.val);
        System.out.println(treeNode.right.val);
    }


    public static TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0) {
            return null;
        }
        //数组折半
        int middle = nums.length/2;
        TreeNode tn = new TreeNode(nums[middle]);


        //左子树递归
        tn.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,middle));
        //右子树递归
        tn.right = sortedArrayToBST(Arrays.copyOfRange(nums,middle+1,nums.length));
        return tn;
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}