面试题 04.02. 最小高度树

关于二叉搜索树的概念。

解法一：递归

保证树的高度最小的原则是构造一棵平衡二叉搜索树，原序列已经有序排列，每次取中值作为根结点，递归构造子树。

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