【亡羊补牢】挑战数据结构与算法 第37期 LeetCode 108. 将有序数组转换为二叉搜索树(二叉树)
发布日期:2021-06-29 14:34:16
浏览次数:2
分类:技术文章
本文共 1228 字,大约阅读时间需要 4 分钟。
仰望星空的人,不应该被嘲笑
题目描述
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
题目要求高度平衡——构建 root 时,选数组的中间元素作为 root 节点值,即可保证平衡。
类似分治算法一样,对中间位置确定根节点 root ,然后递归左子树和右子树,最终走完后就是我们的高度平衡的子树。
参考 大佬题解
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** * @param {number[]} nums * @return {TreeNode} */var sortedArrayToBST = function (nums) { let buildBST = (nums, start, end) => { if (start > end) return null; // 找到中间位置 let mid = (start + end) >>> 1; // 创建根节点 let root = new TreeNode(nums[mid]); // 构建左子树 root.left = buildBST(nums, start, mid - 1); // 构建右子树 root.right = buildBST(nums, mid + 1, end); return root; } return buildBST(nums,0,nums.length-1);};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108781009 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月12日 19时50分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
2020年电赛题目,命题专家权威解析!
2019-04-29
如何掌握“所有”的程序语言?没错,就是所有!
2019-04-29
39岁单身程序员入住养老院
2019-04-29
写论文,这个神器不能少!
2021-07-02
我在哥大读博的五年,万字总结
2021-07-02
本科、硕士、博士,究竟有何区别?
2021-07-02
如果我的实验室也这样布置,那多好。
2021-07-02
现在做硬件工程师还有前途吗?
2021-07-02
用 50 种编程语言写“Hello,World!”
2021-07-02
GD32替换STM32,这些细节一定要知道。
2021-07-02
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2021-07-02
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29