二叉树的层序遍历

难度:

标签:

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

代码结果

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

/*
 * 题目思路：
 * 使用Java Stream实现二叉树的层序遍历。虽然Stream不是典型的队列操作，
 * 但是我们可以通过Stream和队列的结合来完成这个操作。我们仍然需要逐层处理节点，
 * 并将节点的值收集到列表中。
 */
 
import java.util.*;
import java.util.stream.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}
 
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<TreeNode> currentLevelNodes = new ArrayList<>();
            while (!queue.isEmpty()) currentLevelNodes.add(queue.poll());
            result.add(currentLevelNodes.stream().map(node -> node.val).collect(Collectors.toList()));
            currentLevelNodes.forEach(node -> {
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            });
        }
        return result;
    }
}

解释

方法:

这个题解使用广度优先搜索（BFS）的方法来实现二叉树的层序遍历。具体思路是：使用一个队列来存储每一层的节点，每次处理一层节点时，将该层节点的值存储到一个列表中，然后将这个列表添加到结果列表中。在处理完一层节点后，将下一层的节点加入队列，直到队列为空，即遍历完整棵树。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在将节点添加到队列时，如何确保节点按照从左到右的顺序被处理？

▷

在二叉树的层序遍历中，每次从队列中取出节点时，首先取出左子节点，然后是右子节点，并将它们依次添加到队列的尾部。这样，队列始终保持从左到右的顺序，确保每一层都是按从左到右的顺序处理节点。

🦆

如果树中存在值为`null`的节点，该如何处理以保证层序遍历的正确性？

▷

在二叉树的表示中，通常不会在队列中插入值为`null`的节点。节点的值为`null`通常表示该节点不存在。因此，在将子节点加入队列之前，应先检查它们是否为`null`。只有非`null`的节点才被添加到队列中，这样可以避免处理不存在的节点，并保持层序遍历的正确性。

🦆

为什么选择使用deque而不是其他类型的数据结构来实现队列功能？

▷

在Python中，`deque`（双端队列）提供了从两端以近似O(1)的时间复杂度进行添加和删除操作的能力，这使得它非常适合实现队列功能。相比之下，使用列表作为队列时，从列表的开头删除元素的时间复杂度为O(n)，因为这需要移动所有其它元素。因此，`deque`是一个更高效的选择，可以优化层序遍历的性能。

🦆

在处理非常大的树时，如节点数接近2000，是否有内存溢出的风险，如果有，该如何优化？

▷

在现代计算机系统中，处理具有2000个节点的树通常不会导致内存溢出，因为相对于现代计算机的内存容量来说，这种规模还是很小的。然而，如果处理的树规模非常大，以致于可能影响内存使用，可以考虑使用迭代而非递归的方法来减少调用栈的使用，或者考虑压缩树结构、优化存储或分布式处理树结构等方法。

相关问题

二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100