108 - 将有序数组转换为二叉搜索树(convert-sorted-array-to-binary-search-tree)

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

一 目录

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

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

二 前言

返回目录

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

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-22 07:41:49

results matching ""

    No results matching ""