面试题 04.02. 最小高度树

一时失言乱红尘 2022-12-18 01:58 89阅读 0赞

# 题目来源 #

[https://leetcode-cn.com/problems/minimum-height-tree-lcci/][https_leetcode-cn.com_problems_minimum-height-tree-lcci]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

## 第一种解法 ##

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

func sortedArrayToBST(nums []int) *TreeNode {
        
    	if len(nums) == 0{
        
    		return nil
    	}
    
    	if len(nums) == 1  {
        
    		return &TreeNode{
        
    			Val:   nums[0],
    			Left:  nil,
    			Right: nil,
    		}
    	}
    
    	mid := len(nums)/2
    	node := &TreeNode{
        
    		Val:   nums[mid],
    	}
    	node.Left = sortedArrayToBST(nums[:mid])
    	node.Right = sortedArrayToBST(nums[mid+1:])
    
    
    
    	return node
    }

![在这里插入图片描述][20201024223931140.png_pic_center]

[https_leetcode-cn.com_problems_minimum-height-tree-lcci]: https://leetcode-cn.com/problems/minimum-height-tree-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/5872e55ad45c43d4aa02545308ae10cd.png
[20201024223931140.png_pic_center]: /images/20221122/06f00c1713774b758fb256349683cdac.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关最小高度树

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关最小生成树的简单题

古老的最小生成树代码，可以当板子用（针对问题修改一下，不通用，原理一样）。 include <iostream> include <cstdio> i

妖狐艹你老母/ 2022年12月01日 15:39/ 0 赞/ 139 阅读

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

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

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

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

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

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

相关 CSS 最小高度

最小高度 DEMO 效果图最小高度就是给div一个最小高度内容很少的时候占据最小高度多的话

傷城~/ 2022年09月23日 10:52/ 0 赞/ 166 阅读