LeetCode 面试题 04.02. 最小高度树

小灰灰 2022-12-05 10:22 162阅读 0赞

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

思路是由于要创建高度最小的二叉树，并且输入数组是有序的，因此可以先找出中间元素，令其作为根节点，然后对该元素的左边数组和右边数组执行相同的步骤，直到的子数组中只有一个元素或没有元素为止：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        TreeNode *sortedArrayToBSTCore(int start, int end, vector<int> &nums) { 
            if (start > end) {     // 当子数组为空时
                return nullptr;
            }
            
            if (start == end) {     // 当子数组中只有一个元素时
                TreeNode *node = new TreeNode(nums[start]);
                return node;
            }
    
            int middle = (start + end) >> 1;
            TreeNode *node = new TreeNode(nums[middle]);
            node->left = sortedArrayToBSTCore(start, middle - 1, nums);
            node->right = sortedArrayToBSTCore(middle + 1, end, nums);
            return node;
        }
       
        TreeNode* sortedArrayToBST(vector<int>& nums) { 
            int len = nums.size();
            if (len == 0) { 
                return nullptr;
            }
            return sortedArrayToBSTCore(0, len - 1, nums);
        }
    };

时间复杂度为O（n）；由于使用了递归，每一个元素都会在一个栈内转换为对应的节点，因此空间复杂度为O（n）。

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关拓扑排序变种题：Leetcode310最小高度树

拓扑排序变种题：Leetcode310最小高度树问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

末蓝、/ 2023年10月06日 09:22/ 0 赞/ 14 阅读

相关程序员面试金典-面试题04.02-最小高度树

程序员面试金典-面试题04.02-最小高度树上周实现了一个二叉查找树（BST），感觉对于二叉树的操作更加熟练了，然后就找“程序员面试金典”相对应的二叉树的题目，做了四道

╰+攻爆jí腚メ/ 2023年01月10日 11:59/ 0 赞/ 156 阅读

相关 Leetcode310. 最小高度树--基于拓扑排序求解此问题

Leetcode310. 最小高度树–基于拓扑排序求解此问题思想:由边界向中心逐渐收缩，直至收缩到最里层。 class Solution {

淡淡的烟草味﹌/ 2023年01月09日 03:57/ 0 赞/ 133 阅读

相关最小高度树

> leetcode 310 题 \[medium\] > 中: [最小高度树][Link 1] > 英: [Minimum Height Trees][] > !

朱雀/ 2022年12月23日 13:28/ 0 赞/ 145 阅读

相关面试题 04.02. 最小高度树

题目来源 [https://leetcode-cn.com/problems/minimum-height-tree-lcci/][https_leetcode-cn.c

一时失言乱红尘/ 2022年12月18日 01:58/ 0 赞/ 127 阅读

相关 leetcode 310. 最小高度树拓扑排序

使用邻接矩阵会超时使用邻接表就不超时了每次去掉度为1的点到最后的两个以内的时候停止 define debug(x) cout<<x<<": "<<(

偏执的太偏执、/ 2022年12月16日 05:54/ 0 赞/ 137 阅读

相关 LeetCode面试题 04.02. 最小高度树 JAVA

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例: 给定有序数组: [-10,-3,0,5,9],

痛定思痛。/ 2022年12月13日 04:54/ 0 赞/ 136 阅读

相关 LeetCode 面试题 04.02. 最小高度树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。思路是由于要创建高度最小的二叉树，并且输入数组是有序的，因此可以先找出中间元素，

小灰灰/ 2022年12月05日 10:22/ 0 赞/ 163 阅读

相关 310. 最小高度树（JS实现）

1 题目 > 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函

忘是亡心i/ 2022年11月27日 15:59/ 0 赞/ 152 阅读

相关 LeetCode | 面试题 04.02. 最小高度树【Python】

问题 [力扣][Link 1] 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例: 给定有序数组: [-1

曾经终败给现在/ 2022年11月08日 14:08/ 0 赞/ 145 阅读