龙华做网站 熊掌号,专业网站建设比较好,娱乐城网站建设,做游戏制作 网站对于算法题#xff0c;按题型类别刷题才会更有成效#xff0c;因此我这里在网上搜索并参考了下 “#x1f525; LeetCode 热题 HOT 100” 的题型归类#xff0c;并在其基础上做了一定的完善#xff0c;希望能够记录自己的刷题历程#xff0c;有所收获#xff01;点击下发…对于算法题按题型类别刷题才会更有成效因此我这里在网上搜索并参考了下 “ LeetCode 热题 HOT 100” 的题型归类并在其基础上做了一定的完善希望能够记录自己的刷题历程有所收获点击下发链接跳转~⬇️⬇️⬇️ LeetCode 热题 HOT 100【题型归类汇总助力刷题】 108. 将有序数组转换为二叉搜索树 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1 输入nums [-10,-3,0,5,9]
输出[0,-3,9,-10,null,5]
解释[0,-10,5,null,-3,null,9] 也将被视为正确答案 示例 2 输入nums [1,3]
输出[3,1]
解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。提示 1 nums.length 104-104 nums[i] 104nums 按 严格递增 顺序排列 思路参考 LeetCode题解
二叉搜索树BST 的【中序遍历】是升序的因此本题等同于根据中序遍历的序列恢复二叉搜索树 虽然我们可以以升序序列中的任一个元素作为根节点 但是因为本题要求【高度平衡】因此我们需要选择升序序列的【中间元素】作为根节点奥
时间复杂度O(n)其中 n 是数组的长度。每个数字只访问一次。
空间复杂度O(logn)其中 n 是数组的长度。空间复杂度不考虑返回值因此空间复杂度主要取决于递归栈的深度递归栈的深度是 O(logn)。
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
// 参考题解https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/313508/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/?envTypestudy-plan-v2envIdtop-100-liked
// BST 的【中序遍历】是升序的因此本题等同于根据中序遍历的序列恢复二叉搜索树
// 虽然我们可以以升序序列中的任一个元素作为根节点
// 但是因为本题要求【高度平衡】因此我们需要选择升序序列的【中间元素】作为根节点奥
func sortedArrayToBST(nums []int) *TreeNode {var dfs func(l, r int) *TreeNodedfs func(l, r int) *TreeNode {if l r {return nil}mid : l (r-l)/2root : TreeNode{}root.Val nums[mid]root.Left dfs(l, mid-1) // r向左即中间位置移动root.Right dfs(mid1, r) // l向右即向中间位置移动return root}return dfs(0, len(nums)-1)
}
题目扩展
109. 有序链表转换二叉搜索树将本题的数组换成了链表做法完全一样不过链表无法像数组一样直接索引到中间元素链表找中间节点可以用快慢指针法详见876. 链表的中间结点。
