手撸二叉树之最小高度树

前言

咱们继续来刷二叉树，今天要讲的是如果构建最小高度的树。

题目

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

示例

解题思路

首先我们先复习一下二叉搜索树的定义：对于树中的所有子树，左子树上的值都小于根节点的值，右子树上的值都大于根节点上的值。通过中序遍历可以得到一个升序序列。

那如何保证高度最小呢？

既然是要构成深度最小的数，那么数就应该尽可能的饱满，当树中的任意结点的左右子树高度差都不超过 1 时，整棵树的深度最小，所以我们就选择数组的中间点，那么左边和右边都是同样的大小。

下面是一种构造最小高度树的思路：

1. 如果序列长度为 0，那么是一棵空树。
2. 如果序列长度为 1，那么只有一个根节点。
3. 如果长度大于 1，那么选取中间位置的数赋给根节点，然后前一半递归构建左子树，后一半递归构建右子树。

代码实现

/**
 * 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) {
        // 序列长度为 0，那么是一棵空树。
        if (nums.length == 0) {
            return null;
        }

        return createMinHeightBST(nums, 0, nums.length-1);
    }

    public TreeNode createMinHeightBST(int[] nums, int start, int end){
        if (start > end) {
            return null;
        }
        // 选取中间位置
        int mid = (start + end) >> 1;
        //填充根节点
        TreeNode root = new TreeNode(nums[mid]);
        //构造左子树
        root.left = createMinHeightBST(nums, start, mid - 1);
        //构造右子树
        root.right = createMinHeightBST(nums, mid + 1, end);
        return root;
    }
}

最后

复杂度分析：

1. 数组中的元素都使用1次，时间复杂度为O(n).

2. 递归使用栈辅助空间，空间复杂度O(log(n)).