107 - 二叉树的层次遍历II(binary-tree-level-order-traversal-ii)

Create by jsliang on 2019-06-14 17:56:48
Recently revised in 2019-6-14 22:19:59

一 目录

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

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 解题思路

二 前言

返回目录

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:
[
  [15,7],
  [9,20],
  [3]
]

三 解题

返回目录

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

  • 解题代码
var levelOrderBottom = function(root) {
  if (!root) {
    return [];
  }
  let result = [];
  let ergodic = function(root, depth) {
    if (!root) {
      return;
    }
    if (root.val != null) {
      if (!result[depth]) {
        result[depth] = [];
      }
      result[depth] = [root.val, ...result[depth]];
      depth += 1;
      ergodic(root.right, depth);
      ergodic(root.left, depth);
    }
  };
  ergodic(root, 0);
  return result.reverse();
};

四 执行测试

返回目录

  • 参数 root
let root = {
  val: 3,
  left: { val: 9, left: null, right: null, },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
};
  • 返回值 return
[ [ 15, 7 ], [ 9, 20 ], [ 3 ] ]

五 LeetCode Submit

返回目录

✔ Accepted
  ✔ 34/34 cases passed (88 ms)
  ✔ Your runtime beats 86.53 % of javascript submissions
  ✔ Your memory usage beats 5.59 % of javascript submissions (37 MB)

六 解题思路

返回目录

又到了每日解题的时间。

首先,如果 root 是空的话,就返回 []

if (!root) {
  return [];
}

然后,我们设置 result 来返回结果。

let result = [];

接着,我们开始递归之旅:

  • 步骤 1:如果节点没有下一个了,那么我们终止递归。
if (!root) {
  return;
}
  • 步骤 2:如果 root.val 存在值,那么我们设置 result
if (!result[depth]) {
  result[depth] = [];
}
result[depth] = [root.val, ...result[depth]];

小伙伴们可能比较在意这两段 JS 的作用,那么我们讲解下,先看树结构:

  3
 / \
9  20
  /  \
 15   7

假设,我们现在 result: [],我们递归第一遍,那么 result[1] 是不是要开辟一个数组空间,即:result: [[]]。然后通过 [a, ...b] 的形式,将数组扩展开来,即:[3, ...[]],结果自然而然就是 [3] 了,所以 result 变成:result: [[3]]

当我们递归第二遍的时候,我们先遍历的是右节点,故 result:[[3], [20]]……以此递归:

[]
[ [ 3 ] ]
[ [ 3 ], [ 20 ] ]
[ [ 3 ], [ 20 ], [ 7 ] ]
[ [ 3 ], [ 20 ], [ 15, 7 ] ]

最后,我们通过 return result.reverse(),将数组反转并返回出去,从而得到倒序结果:

[ [ 15, 7 ], [ 9, 20 ], [ 3 ] ]

我们就完成了对应的攻略。


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

图

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-14 22:24:58

results matching ""

    No results matching ""