本文主要是介绍LeetCode题练习与总结：二叉树的层序遍历Ⅱ--107，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
二、解题思路
这个问题是关于如何对二叉树进行自底向上的层序遍历。我们可以使用一个队列来进行广度优先搜索（BFS），并使用一个变量来记录当前层的节点值。在遍历每一层的时候，我们使用一个双端队列（Deque）来存储当前层的节点值，这样我们就可以从双端队列的尾部开始遍历，从而实现自底向上的层序遍历。
算法步骤：
- 初始化一个空队列
queue用于BFS，以及一个空的双端队列deque用于存储当前层的节点值。 - 如果
root不为空，则将其加入queue。 - 初始化一个变量
level为0，用于标识当前层的奇偶性。 - 当
queue不为空时，进行以下操作： a. 获取当前层的节点数量size（即queue的长度）。 b. 遍历当前层的节点，对于每个节点： i. 从queue中移除节点，并将其值加入deque的头部（如果level为偶数）或尾部（如果level为奇数）。 ii. 如果该节点的左子节点不为空，将其加入queue。 iii. 如果该节点的右子节点不为空，将其加入queue。 c. 将deque转换为列表，并加入结果列表result。 d. 将level加1，清空deque。 - 返回结果列表
result。
三、具体代码
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int level = 0;while (!queue.isEmpty()) {int size = queue.size();Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node != null) {deque.offerLast(node.val);queue.offer(node.left);queue.offer(node.right);}}if (!deque.isEmpty()) {result.add(0, new ArrayList<>(deque));}}return result;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
levelOrderBottom函数会对每个节点进行一次操作，其中n是树中节点的数量。- 因此，总的时间复杂度是 O(n)。
2. 空间复杂度
- 空间复杂度主要取决于队列和双端队列中存储的节点数量。
- 在最坏的情况下，树是完全不平衡的，例如每个节点都只有左子节点或者只有右子节点，此时队列和双端队列中存储的节点数量最多，为 O(n)。
- 因此，总的空间复杂度是 O(n)。
综上所述，代码的时间复杂度是 O(n)，空间复杂度也是 O(n)，其中 n 是树中节点的数量。
五、总结知识点
-
队列（Queue）的使用：代码中使用了
LinkedList类作为Queue的实现，用于在BFS中存储待遍历的节点。队列遵循先进先出（FIFO）的原则。 -
递归：虽然代码中没有直接使用递归，但BFS本质上是一种递归的过程，通过循环模拟递归的调用栈。
-
双端队列（Deque）的使用：代码中使用了
LinkedList类作为Deque的实现，用于在每一层遍历时存储当前层的节点值。双端队列可以同时从两端添加或删除元素。 -
迭代与循环：使用
while循环来迭代遍历树的每一层，直到队列为空。 -
条件语句：使用
if-else语句来判断节点是否为空，以及判断队列是否为空。 -
数据结构转换：使用
ArrayList和LinkedList之间的转换，将Deque中的元素转换为一个List，然后添加到结果List中。 -
布尔变量的使用：使用布尔变量
level来标志当前层的奇偶性，并在每层遍历后取反。 -
树节点的定义：代码中使用了
TreeNode类来定义二叉树的节点，每个节点包含一个整数值和指向左右子节点的引用。 -
函数返回值：
levelOrderBottom函数返回一个包含多层的List<List<Integer>>，表示二叉树的自底向上的层序遍历结果。 -
边界条件的处理：在函数开始时检查
root是否为空，如果为空则直接返回一个空列表。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
这篇关于LeetCode题练习与总结：二叉树的层序遍历Ⅱ--107的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
