LeetCode 第 107 号问题:二叉树的层次遍历 II

本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。

个人网站:https://www.cxyxiaowu.com

题目来源于 LeetCode 上第 107 号问题:二叉树的层次遍历 II。题目难度为 Easy,目前通过率为 55.8% 。

题目描述

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

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

    3
   / \
  9  20
    /  \
   15   7

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

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

题目解析

该问题需要用到队列,解法与上篇每天一算:Binary Tree Level Order Traversal类似,区别在于最后存储方式的不同。

  • 建立一个 queue
  • 先把根节点放进去,这时候找根节点的左右两个子节点
  • 去掉根节点,此时queue里的元素就是下一层的所有节点
  • 用 for 循环遍历,将结果存到一个一维向量里
  • 遍历完之后再把这个一维向量插入到二维向量里
  • 以此类推,可以完成层序遍历

动画描述

代码实现

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 第 107 号问题:二叉树的层次遍历 II

我还会在以下平台发布内容

GitHub 哔哩哔哩