LeetCode - 108 - 将有序数组转换为二叉搜索树

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 108 - 将有序数组转换为二叉搜索树

Create by jsliang on 2019-06-17 08:57:03
Recently revised in 2019-6-22 07:41:48

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | |  3.1 解法 - 后序遍历 | |  3.2 解法 - 后序遍历(简化) |

二 前言

  • 难度:简单

  • 涉及知识:树、深度优先搜索

  • 题目地址:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

  • 题目内容

  1. 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

  2. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

  3. 示例:

  4. 给定有序数组: [-10,-3,0,5,9],

  5. 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

  6. 0

  7. / \

  8. -3 9

  9. / /

  10. -10 5

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 后序遍历

  • 解题代码

  1. var sortedArrayToBST = function(nums) {

  2. let sort = (left, right) => {

  3. if (left > right) {

  4. return null;

  5. }

  6. let m = left + Math.floor((right - left) / 2);

  7. let node = {

  8. val: nums[m],

  9. left: sort(left, m - 1),

  10. right: sort(m + 1, right),

  11. }

  12. return node;

  13. };

  14. return sort(0, nums.length - 1);

  15. };

  • 执行测试

  1. nums: [-10,-3,0,1,5,9]

  2. return

  1. { val: 0,

  2. left:

  3. { val: -10,

  4. left: null,

  5. right: { val: -3, left: null, right: null } },

  6. right:

  7. { val: 5,

  8. left: { val: 1, left: null, right: null },

  9. right: { val: 9, left: null, right: null } } }

  • LeetCode Submit

  1. Accepted

  2. 32/32 cases passed (100 ms)

  3. Your runtime beats 92.7 % of javascript submissions

  4. Your memory usage beats 25.53 % of javascript submissions (37.8 MB)

  • 知识点

  1. Math:JS 中的内置对象,具有数学常数和函数的属性和方法。 Math 详细介绍

  • 解题思路

首先,这次解题涉及到一个名词,叫 后序遍历,希望了解更多的小伙伴,可以百度了解更多,这里仅做简单介绍。

  • 后序遍历后序遍历(LRD)是二叉树遍历的一种,也叫作后根遍历、后序周游。在 后序遍历 中,它会先访问左节点,再访问右节点,最后访问根节点。

话再多还不如上图:

LeetCode - 108 - 将有序数组转换为二叉搜索树

现在,有这样一棵树如上所示,那么,它怎么通过后序遍历来访问节点的呢?

LeetCode - 108 - 将有序数组转换为二叉搜索树

按照我们所说的,遍历步骤是:D -> E -> B -> F -> C -> A。

很好,看到这里,你应该对后续遍历有个大致的映像了,如果你还没通,别急,咱们看代码:

  1. var sortedArrayToBST = function(nums) {

  2. let sort = (left, right) => {

  3. if (left > right) {

  4. return null;

  5. }

  6. let m = left + Math.floor((right - left) / 2);

  7. let node = {

  8. val: nums[m],

  9. left: sort(left, m - 1),

  10. right: sort(m + 1, right),

  11. }

  12. console.log("------");

  13. console.log(`${left} ${right}`);

  14. console.log(node);

  15. return node;

  16. };

  17. return sort(0, nums.length - 1);

  18. };

  19. sortedArrayToBST([-10, -3, 0, 1, 5, 9]);

在这里,我们进行了 console 打印,那么小伙伴可以先想下,它会打印出什么来:

  1. ------

  2. 1 1

  3. { val: -3, left: null, right: null }

  4. ------

  5. 0 1

  6. { val: -10,

  7. left: null,

  8. right: { val: -3, left: null, right: null } }

  9. ------

  10. 3 3

  11. { val: 1, left: null, right: null }

  12. ------

  13. 5 5

  14. { val: 9, left: null, right: null }

  15. ------

  16. 3 5

  17. { val: 5,

  18. left: { val: 1, left: null, right: null },

  19. right: { val: 9, left: null, right: null } }

  20. ------

  21. 0 5

  22. { val: 0,

  23. left:

  24. { val: -10,

  25. left: null,

  26. right: { val: -3, left: null, right: null } },

  27. right:

  28. { val: 5,

  29. left: { val: 1, left: null, right: null },

  30. right: { val: 9, left: null, right: null } } }

OK,看到这里,小伙伴们应该有谱了,是怎么跑起来的。

那么,回归这道题本质,我们还能不能找到其他方法呢?

3.2 解法 - 后序遍历(简化)

  • 解题代码

  1. var sortedArrayToBST = function(nums) {

  2. if (!nums.length) return null;

  3. let mid = Math.floor(nums.length / 2);

  4. let root = {

  5. val: nums[mid],

  6. left: sortedArrayToBST(nums.slice(0, mid)),

  7. right: sortedArrayToBST(nums.slice(mid + 1)),

  8. }

  9. return root;

  10. };

  • 执行测试

  1. nums: [-10,-3,0,1,5,9]

  2. return

  1. { val: 1,

  2. left:

  3. { val: -3,

  4. left: { val: -10, left: null, right: null },

  5. right: { val: 0, left: null, right: null } },

  6. right:

  7. { val: 9,

  8. left: { val: 5, left: null, right: null },

  9. right: null } }

  • LeetCode Submit

  1. Accepted

  2. 32/32 cases passed (108 ms)

  3. Your runtime beats 84.88 % of javascript submissions

  4. Your memory usage beats 66.67 % of javascript submissions (37.5 MB)

  • 知识点

  1. Math:JS 中的内置对象,具有数学常数和函数的属性和方法。 Math 详细介绍

  • 解题思路

经过上面一节的提示,这节小伙伴们可能就需要自己思考了:

  1. var sortedArrayToBST = function(nums) {

  2. if (!nums.length) return null;

  3. let mid = Math.floor(nums.length / 2);

  4. let root = {

  5. val: nums[mid],

  6. left: sortedArrayToBST(nums.slice(0, mid)),

  7. right: sortedArrayToBST(nums.slice(mid + 1)),

  8. }

  9. console.log('------');

  10. console.log(root);

  11. return root;

  12. };

  13. sortedArrayToBST([-10, -3, 0, 1, 5, 9]);

这次打印会输出什么?

  1. ------

  2. { val: -10, left: null, right: null }

  3. ------

  4. { val: 0, left: null, right: null }

  5. ------

  6. { val: -3,

  7. left: { val: -10, left: null, right: null },

  8. right: { val: 0, left: null, right: null } }

  9. ------

  10. { val: 5, left: null, right: null }

  11. ------

  12. { val: 9,

  13. left: { val: 5, left: null, right: null },

  14. right: null }

  15. ------

  16. { val: 1,

  17. left:

  18. { val: -3,

  19. left: { val: -10, left: null, right: null },

  20. right: { val: 0, left: null, right: null } },

  21. right:

  22. { val: 9,

  23. left: { val: 5, left: null, right: null },

  24. right: null } }

这样,我们就完成了本次的解题,下期再会~


不折腾的前端,和咸鱼有什么区别!

LeetCode - 108 - 将有序数组转换为二叉搜索树

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 108 - 将有序数组转换为二叉搜索树

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CSS实战手册

CSS实战手册

David Sawyer McFarland / 俞黎敏 / 电子工业出版社 / 2007-07-01 / 68.00元

CSS是一场革命 借用quirksMode的PPK(Peter-Paul Koch)的话来说:CSS是一场革命。 Ajax的浪潮正在逐步改变着Web开发的方式。谈到Ajax,开发人员似乎更注重于 XMLHttpRequest 和 JavaScript ,而淡忘了Ajax还有一个重要的组成部分 CSS。 事实上,CSS和DOM、xHTML以及粘合它们的JavaScript密不可分,......一起来看看 《CSS实战手册》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换