手撸二叉树之最小高度树｜8月更文挑战

手撸二叉树之最小高度树｜8月更文挑战

前言

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

题目

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

示例

解题思路

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

那如何保证高度最小呢？

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

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

如果序列长度为 0，那么是一棵空树。如果序列长度为 1，那么只有一个根节点。如果长度大于 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{ 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

最后

复杂度分析：

数组中的元素都使用1次，时间复杂度为O(n).递归使用栈辅助空间，空间复杂度O(log(n)).

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。