手撸二叉树之最小高度树

HelloWorld杰少

关注

发布于: 2021 年 08 月 02 日

前言

今天是 8 月更文活动的第 2 天，咱们继续来刷二叉树，今天要讲的是如果构建最小高度的树。

题目

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

示例

解题思路

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

那如何保证高度最小呢？

既然是要构成深度最小的数，那么数就应该尽可能的饱满，当树中的任意结点的左右子树高度差都不超过 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 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 次，时间复杂度为 O(n).
递归使用栈辅助空间，空间复杂度 O(log(n)).

发布于: 2021 年 08 月 02 日阅读数: 11

原文链接:【http://xie.infoq.cn/article/e94dd87ade29362de6e78d2ec】。文章转载请联系作者。

HelloWorld杰少

关注

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

发布

暂无评论

创作场景

手撸二叉树之最小高度树

前言

题目

示例

解题思路

代码实现

最后

HelloWorld杰少

评论