二叉树的层序遍历 II

难度:

标签:

题目描述

给你二叉树的根节点 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

代码结果

运行时间: 44 ms, 内存: 15.1 MB

 
/**
 * 思路：
 * 1. 使用递归进行深度优先搜索（DFS）。
 * 2. 使用一个Map来存储每层的节点。
 * 3. 使用流（stream）对Map进行处理，按层级从高到低排序。
 * 4. 将结果转换为列表返回。
 */
import java.util.*;
import java.util.stream.Collectors;
 
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Map<Integer, List<Integer>> levelMap = new HashMap<>();
        dfs(root, 0, levelMap);
        return levelMap.keySet().stream()
                        .sorted(Comparator.reverseOrder())
                        .map(levelMap::get)
                        .collect(Collectors.toList());
    }
 
    private void dfs(TreeNode node, int level, Map<Integer, List<Integer>> levelMap) {
        if (node == null) return;
        levelMap.computeIfAbsent(level, k -> new ArrayList<>()).add(node.val);
        dfs(node.left, level + 1, levelMap);
        dfs(node.right, level + 1, levelMap);
    }
}
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

解释

方法:

该题解使用 BFS (广度优先搜索) 的思想，通过队列实现。首先将根节点入队，然后逐层遍历二叉树。对于每一层，先统计队列中的节点数(即当前层的节点数)，然后将这些节点依次出队并将它们的值记录在当前层的列表中，同时将它们的非空子节点加入队列，继续下一轮迭代。由于题目要求自底向上输出结果，所以在 BFS 过程中，我们需要把每一层的结果添加到结果列表的头部。最后返回结果列表即可。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在使用BFS进行层序遍历时，你是如何处理树中存在的null值，以确保它们不会被加入到队列中的？

▷

在BFS层序遍历的过程中，只有非空的子节点才会被加入到队列中。在代码里，每次从队列中取出一个节点后，会检查这个节点的左右子节点是否存在（即不为null）。只有当子节点非空时（`if node.left:` 和 `if node.right:`），这些子节点才会被添加到队列中。这样，队列中永远不会包含null值，只包含实际存在的TreeNode对象。

🦆

为什么在结果列表中使用res.append(floor)然后返回res[::-1]，而不是直接使用res.insert(0, floor)来实现自底向上的层序遍历？

▷

使用`res.append(floor)`后再通过`res[::-1]`返回结果的方式比直接使用`res.insert(0, floor)`更为高效。这是因为列表的`append`操作是O(1)的，即在列表的末尾添加元素的时间复杂度是常数。而`insert(0, floor)`操作是O(n)的，因为它需要在列表的开始位置插入元素，这会导致已有元素都要向后移动一位。因此，虽然两种方法都能实现自底向上的层序遍历，但前者在性能上更优，特别是在处理大数据时差异更为明显。

🦆

代码中提到，每个节点都会被访问一次，这对于所有类型的二叉树结构都是适用的吗？请问有没有例外情况？

▷

BFS层序遍历确实保证了每个节点都会被访问一次，并且这个特性适用于所有类型的二叉树，包括完全二叉树、不完全二叉树、倾斜二叉树等。没有例外情况，因为BFS的遍历逻辑是从根节点开始，逐层向下，每次都从队列中取出当前层的所有节点，同时将它们的子节点加入队列以便下一层的遍历。这种方法确保了每个节点都被精确地访问一次，不会遗漏也不会重复访问。

相关问题