面试题 04.02. 最小高度树

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