LeetCode题解之最小高度树

最小高度树

题目描述

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例 :

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

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

          0 
         / \ 
       -3   9 
       /   / 
     -10  5 

解题思路

二叉树搜索树的特点是任一节点的左子树的值都比该节点的值小，右子树的值都比该节点的值大，因此利用这个特点可知，选取有序数组的中点元素作为根节点，以中点划分的左右子数组作为树的左右子树的这样一棵树即为满足条件的最小高度树，因此利用递归就可以很轻松地创建出一棵这样的最小高度树。

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums 的长度，因为创建最小高度树需要遍历 nums 数组中每个元素一次，因此时间复杂度为 O(n)。
• 空间复杂度：O(n)。

代码实现

/**
 * 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;
        }
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }
}