题目
标题和出处
标题：二叉树的层序遍历 II
出处：107. 二叉树的层序遍历 II
难度
4 级
题目描述
要求
给你二叉树的根结点 root \texttt{root} root，返回其结点值自底向上的层序遍历（即从左到右，按从叶结点所在层到根结点所在层逐层遍历）。
示例
示例 1：
输入：
root
=
[3,9,20,null,null,15,7]
\texttt{root = [3,9,20,null,null,15,7]}
root = [3,9,20,null,null,15,7]
输出：
[[15,7],[9,20],[3]]
\texttt{[[15,7],[9,20],[3]]}
[[15,7],[9,20],[3]]
示例 2：
输入：
root
=
[1]
\texttt{root = [1]}
root = [1]
输出：
[[1]]
\texttt{[[1]]}
[[1]]
示例 3：
输入：
root
=
[]
\texttt{root = []}
root = []
输出：
[]
\texttt{[]}
[]
数据范围
- 树中结点数目在范围 [0, 2000] \texttt{[0, 2000]} [0, 2000] 内
- -1000 ≤ Node.val ≤ 1000 \texttt{-1000} \le \texttt{Node.val} \le \texttt{1000} -1000≤Node.val≤1000
解法
思路和算法
这道题和「二叉树的层序遍历」相似，区别在于这道题要求按自底向上的顺序返回层序遍历的结果。
从根结点开始依次遍历每一层的结点，对于每一层维护一个结点值序列。由于这道题要求按自底向上的顺序返回层序遍历的结果，因此遍历完每一层结点之后，将该层结点值序列添加到层序遍历序列的头部。
为了在 O ( 1 ) O(1) O(1) 时间内完成将一层结点值序列添加到层序遍历序列的头部，层序遍历序列应使用链表，在链表头部添加元素的时间是 O ( 1 ) O(1) O(1)。
代码
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> levelOrderTraversal = new LinkedList<List<Integer>>();
if (root == null) {
return levelOrderTraversal;
}
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> levelValues = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
levelValues.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
levelOrderTraversal.add(0, levelValues);
}
return levelOrderTraversal;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉树的结点数。每个结点都被访问一次，层序遍历序列使用链表时，每次将一层结点值序列添加到层序遍历序列的头部的时间是 O ( 1 ) O(1) O(1)，因此总时间复杂度是 O ( n ) O(n) O(n)。文章来源：https://www.toymoban.com/news/detail-671118.html
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间，队列内元素个数不超过 n n n。文章来源地址https://www.toymoban.com/news/detail-671118.html
到了这里，关于二叉树题目：二叉树的层序遍历 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
