429 - n叉树的层序遍历(n-ary-tree-level-order-traversal)

Create by jsliang on 2019-07-25 19:16:54
Recently revised in 2019-07-26 10:10:42

一 目录

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

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

二 前言

返回目录

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

例如,给定一个 3叉树 :

      1
    /   \
  3   2   4
 / \
5   6

返回其层序遍历:

[
  [1],
  [3,2,4],
  [5,6]
]


说明:

树的深度不会超过 1000。
树的节点总数不会超过 5000。

三 解题

返回目录

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

  • 解题代码
const levelOrder = (root, deep = -1, result = []) => {
  if (!root) {
    return [];
  }
  deep++;
  if (!result[deep]) {
    result[deep] = [root.val];
  } else {
    result[deep].push(root.val);
  }
  for (let i = 0; i < root.children.length; i++) {
    levelOrder(root.children[i], deep, result);
  }
  return result;
}

四 执行测试

返回目录

  • root
const root = {
  val: 1,
  $id: 1,
  children: [{
    val: 3,
    $id: 2,
    children: [{
      val: 5,
      $id: 5,
      children: [],
    }, {
      val: 6,
      $id: 6,
      children: [],
    }],
  }, {
    val: 2,
    $id: 3,
    children: [],
  }, {
    val: 4,
    $id: 4,
    children: [],
  }],
};
  • return
[ [ 1 ], [ 3, 2, 4 ], [ 5, 6 ] ]

五 LeetCode Submit

返回目录

✔ Accepted
  ✔ 36/36 cases passed (908 ms)
  ✔ Your runtime beats 94.22 % of javascript submissions
  ✔ Your memory usage beats 5.26 % of javascript submissions (87.7 MB)

六 知识点

返回目录

  1. push()push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。push() 详细介绍

七 解题思路

返回目录

首先,看到树,不要管是什么树,我们先回想公式:

const ergodic = (root) => {
  if (!root) {
    return;
  }
  ergodic(root.left);
  ergodic(root.right);
}

然后,现在它变得高级了,要做 n 叉树,那么我们就:

const levelOrder = (root) => {
  let result = [];
  const ergodic = (root, deep) => {
    if (!root) {
      return;
    }
    deep++;
    if (!result[deep]) {
      result[deep] = [root.val];
    } else {
      result[deep].push(root.val);
    }
    for (let i = 0; i < root.children.length; i++) {
      ergodic(root.children[i], deep);
    }
  }
  ergodic(root, -1);
  return result;
};
  1. 定义 result 来接收最终成果。
  2. 定义 ergodic 来遍历树。它接受两个参数:root 表示为树当前节点;deep 表示树的层级。
  3. 调用 ergodic(root, -1) 初始化值。
  4. 每次递归,deep 进行 +1 操作,表明树又深了一层。
  5. 如果当前树深度下,result[deep] 是空,那么我们就需要初始化该 result[deep] 的值为 [root.val];如果不为空,则直接使用 push() 方法。
  6. 遍历当前树所有的子节点,直至结束。

光说小伙伴们可能懵逼,我们打印下遍历:

------
{ '$id': 1,
  children:
   [ { '$id': 2, children: [Array], val: 10 },
     { '$id': 5, children: [Array], val: 3 } ],
  val: 1 }
0
------
{ '$id': 2,
  children:
   [ { '$id': 3, children: [], val: 5 },
     { '$id': 4, children: [], val: 0 } ],
  val: 10 }
1
------
{ '$id': 3, children: [], val: 5 }
2
------
{ '$id': 4, children: [], val: 0 }
2
------
{ '$id': 5,
  children: [ { '$id': 6, children: [], val: 6 } ],
  val: 3 }
1
------
{ '$id': 6, children: [], val: 6 }
2

接着,我们就可以看到最终成果啦:

[ [ 1 ], [ 10, 3 ], [ 5, 0, 6 ] ]

成果破解本题。

最后,我们再完善下题解,优化优化:

const levelOrder = (root, deep = -1, result = []) => {
  if (!root) {
    return [];
  }
  deep++;
  if (!result[deep]) {
    result[deep] = [root.val];
  } else {
    result[deep].push(root.val);
  }
  for (let i = 0; i < root.children.length; i++) {
    levelOrder(root.children[i], deep, result);
  }
  return result;
}

Submit 提交:

✔ Accepted
  ✔ 36/36 cases passed (908 ms)
  ✔ Your runtime beats 94.22 % of javascript submissions
  ✔ Your memory usage beats 5.26 % of javascript submissions (87.7 MB)

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

图

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-07-26 10:10:43

results matching ""

    No results matching ""