专栏首页前端小书童一天一大 lee(二叉树的层次遍历 II)难度:简单-Day20200906

一天一大 lee(二叉树的层次遍历 II)难度:简单-Day20200906

题目:

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:

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

抛砖引玉

抛砖引玉

思路

二叉树遍历:

  • 广度优先搜索(BFS),将待遍历的元素存放到数组中,一层层遍历
  • 深度优先搜索(DFS),选择一个元素将其遍历至最里层

可以发现其实广度优先搜索的逻辑更符合本题要要求。

广度优先搜索(BFS)

从根节点开始遍历,遍历一个元素就将其从queue中取出,将其下一层放入queue中待下次遍历

每一层遍历均记录子元素数组,且存放到结果数组中

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
  let _result = [],
      queue = [];
  if (root == null) return [];
  queue.push(root);

  while (queue.length) {
    let len = queue.length,
        levelNodes = [];
    for (let i = 0; i < len; i++) {
      let node = queue.shift();
      levelNodes.push(node.val);
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
    _result.push(levelNodes);
  }
  return _result.reverse();
};

深度优先搜索(DFS)

边遍历边生成结果数组

递归:

  • 参数:待遍历的节点,当前节点属于的层级数
  • 终止:传入的节点为null
var levelOrderBottom = function(root) {
  let _result = [];
  if (root == null) return [];
  function dfs(node, level) {
    if (!node) return
    if (_result[level]) {
      _result[level].push(node.val)
    } else {
      _result[level] = [node.val];
    }
    level++;
    dfs(node.left, level);
    dfs(node.right, level);
  }
  dfs(root, 0)
  return _result.reverse();
};

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】二叉树的前序遍历 (难度:中等) - Day20201027

    前端小书童
  • 【一天一大 lee】二叉搜索树的最小绝对差 (难度:简单) - Day20201012

    给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

    前端小书童
  • 【一天一大 lee】求根到叶子节点数字之和 (难度:中等) - Day20201029

    给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

    前端小书童
  • 【二叉树打卡2】从上往下打印二叉树

    这个像相当于二叉树四种遍历中的层序遍历了,其思想是采用广度优先遍历,借助一个辅助队列,步骤如下:

    帅地
  • 剑指Offer-重建二叉树

    题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

    武培轩
  • 完美假期第一步:用Python寻找最便宜的航班!

    这个简单的问题经常会得到一个积极的回复甚至还会额外收到一个或两个冒险的故事。通常来讲,旅行是一种体验新文化和拓宽自己视野的好方法。

    CDA数据分析师
  • 完美假期第一步:用Python寻找最便宜的航班!

    这个简单的问题经常会得到一个积极的回复甚至还会额外收到一个或两个冒险的故事。通常来讲,旅行是一种体验新文化和拓宽自己视野的好方法。

    abs_zero
  • 爬虫课程(一)|课程介绍和安排

    黄小怪
  • 网络爬虫的应用领域

    学一学大数据
  • (译)SDL编程入门(8)几何图形渲染

    除了新的纹理API,SDL还有新的基元渲染调用作为其渲染API[1]的一部分。因此,如果你需要渲染一些基本的形状,而你又不想为它们创建额外的图形,SDL可以为你...

    arcticfox

扫码关注云+社区

领取腾讯云代金券