内容简介: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。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
三 解题
小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。
3.1 解法 - 后序遍历
解题代码:
var sortedArrayToBST = function(nums) {
let sort = (left, right) => {
if (left > right) {
return null;
}
let m = left + Math.floor((right - left) / 2);
let node = {
val: nums[m],
left: sort(left, m - 1),
right: sort(m + 1, right),
}
return node;
};
return sort(0, nums.length - 1);
};
执行测试:
nums
:[-10,-3,0,1,5,9]
return
:
{ val: 0,
left:
{ val: -10,
left: null,
right: { val: -3, left: null, right: null } },
right:
{ val: 5,
left: { val: 1, left: null, right: null },
right: { val: 9, left: null, right: null } } }
LeetCode Submit:
√ Accepted
√ 32/32 cases passed (100 ms)
√ Your runtime beats 92.7 % of javascript submissions
√ Your memory usage beats 25.53 % of javascript submissions (37.8 MB)
知识点:
Math
:JS 中的内置对象,具有数学常数和函数的属性和方法。Math
详细介绍
解题思路:
首先,这次解题涉及到一个名词,叫 后序遍历,希望了解更多的小伙伴,可以百度了解更多,这里仅做简单介绍。
后序遍历:后序遍历(LRD)是二叉树遍历的一种,也叫作后根遍历、后序周游。在 后序遍历 中,它会先访问左节点,再访问右节点,最后访问根节点。
话再多还不如上图:
现在,有这样一棵树如上所示,那么,它怎么通过后序遍历来访问节点的呢?
按照我们所说的,遍历步骤是:D -> E -> B -> F -> C -> A。
很好,看到这里,你应该对后续遍历有个大致的映像了,如果你还没通,别急,咱们看代码:
var sortedArrayToBST = function(nums) {
let sort = (left, right) => {
if (left > right) {
return null;
}
let m = left + Math.floor((right - left) / 2);
let node = {
val: nums[m],
left: sort(left, m - 1),
right: sort(m + 1, right),
}
console.log("------");
console.log(`${left} ${right}`);
console.log(node);
return node;
};
return sort(0, nums.length - 1);
};
sortedArrayToBST([-10, -3, 0, 1, 5, 9]);
在这里,我们进行了 console
打印,那么小伙伴可以先想下,它会打印出什么来:
------
1 1
{ val: -3, left: null, right: null }
------
0 1
{ val: -10,
left: null,
right: { val: -3, left: null, right: null } }
------
3 3
{ val: 1, left: null, right: null }
------
5 5
{ val: 9, left: null, right: null }
------
3 5
{ val: 5,
left: { val: 1, left: null, right: null },
right: { val: 9, left: null, right: null } }
------
0 5
{ val: 0,
left:
{ val: -10,
left: null,
right: { val: -3, left: null, right: null } },
right:
{ val: 5,
left: { val: 1, left: null, right: null },
right: { val: 9, left: null, right: null } } }
OK,看到这里,小伙伴们应该有谱了,是怎么跑起来的。
那么,回归这道题本质,我们还能不能找到其他方法呢?
3.2 解法 - 后序遍历(简化)
解题代码:
var sortedArrayToBST = function(nums) {
if (!nums.length) return null;
let mid = Math.floor(nums.length / 2);
let root = {
val: nums[mid],
left: sortedArrayToBST(nums.slice(0, mid)),
right: sortedArrayToBST(nums.slice(mid + 1)),
}
return root;
};
执行测试:
nums
:[-10,-3,0,1,5,9]
return
:
{ val: 1,
left:
{ val: -3,
left: { val: -10, left: null, right: null },
right: { val: 0, left: null, right: null } },
right:
{ val: 9,
left: { val: 5, left: null, right: null },
right: null } }
LeetCode Submit:
✔ Accepted
✔ 32/32 cases passed (108 ms)
✔ Your runtime beats 84.88 % of javascript submissions
✔ Your memory usage beats 66.67 % of javascript submissions (37.5 MB)
知识点:
Math
:JS 中的内置对象,具有数学常数和函数的属性和方法。Math
详细介绍
解题思路:
经过上面一节的提示,这节小伙伴们可能就需要自己思考了:
var sortedArrayToBST = function(nums) {
if (!nums.length) return null;
let mid = Math.floor(nums.length / 2);
let root = {
val: nums[mid],
left: sortedArrayToBST(nums.slice(0, mid)),
right: sortedArrayToBST(nums.slice(mid + 1)),
}
console.log('------');
console.log(root);
return root;
};
sortedArrayToBST([-10, -3, 0, 1, 5, 9]);
这次打印会输出什么?
------
{ val: -10, left: null, right: null }
------
{ val: 0, left: null, right: null }
------
{ val: -3,
left: { val: -10, left: null, right: null },
right: { val: 0, left: null, right: null } }
------
{ val: 5, left: null, right: null }
------
{ val: 9,
left: { val: 5, left: null, right: null },
right: null }
------
{ val: 1,
left:
{ val: -3,
left: { val: -10, left: null, right: null },
right: { val: 0, left: null, right: null } },
right:
{ val: 9,
left: { val: 5, left: null, right: null },
right: null } }
这样,我们就完成了本次的解题,下期再会~
不折腾的前端,和咸鱼有什么区别!
jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。
扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- PHP运用foreach神奇的转换数组(实例讲解)
- 一个新细节,Go 1.17 将允许切片转换为数组指针
- .NET/C# 将一个命令行参数字符串转换为命令行参数数组 args
- vue学习—Convert HTML string to AST,如何将html字符串转换为ast数组结构
- JavaScript进阶系列-类型转换、隐式类型转换
- Android 多国语言转换 Excel 和 Excel 转换为 string
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。