LeetCode107. 二叉树的层序遍历 II

**二叉树的层序遍历 II**

###问题描述给定一个二叉树，返回其每一层的节点值。

### 示例

输入:3 / 
920  
157输出:[
 [3],
 [9,20],
 [15,7]
]

### 解决方案我们可以使用层序遍历（BFS）来解决这个问题。首先，我们需要将二叉树转换为一个队列，用于存储每一层的节点，然后我们可以按照层序顺序访问这些节点。

#### Java代码示例

javaimport java.util.*;

public class Solution {
 public List> levelOrderBottom(TreeNode root) {
 if (root == null) return new ArrayList<>();

 Queue queue = new LinkedList<>();
 queue.offer(root);

 List> result = new ArrayList<>();

 while (!queue.isEmpty()) {
 int size = queue.size();
 List level = new ArrayList<>();

 for (int i =0; i < size; i++) {
 TreeNode node = queue.poll();

 // 将当前节点的值添加到当前层级中 level.add(node.val);

 if (node.left != null) {
 queue.offer(node.left);
 }
 if (node.right != null) {
 queue.offer(node.right);
 }
 }

 // 将当前层级添加到结果列表中 result.add(0, level); // 将层级添加到最顶部 }

 return result;
 }
}

#### Python代码示例

from collections import dequeclass Solution:
 def levelOrderBottom(self, root):
 if not root:
 return []

 queue = deque([root])
 result = []

 while queue:
 size = len(queue)
 level = []

 for _ in range(size):
 node = queue.popleft()

 # 将当前节点的值添加到当前层级中 level.append(node.val)

 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)

 # 将当前层级添加到结果列表中 result.insert(0, level) # 将层级添加到最顶部 return result

###说明在上述代码示例中，我们首先检查根节点是否为 `null`，如果是，则返回一个空列表。然后，我们创建一个队列来存储每一层的节点，并将根节点添加到队列中。

接下来，我们进入一个循环直到队列为空。在每次迭代中，我们首先记录当前队列中的大小，然后我们开始从队列中取出所有节点并将它们的值添加到当前层级中。然后，我们检查这些节点是否有左或右孩子，如果有，则将它们添加到队列中。

最后，我们将当前层级添加到结果列表中，但由于我们需要将层级按顺序排列，所以我们使用 `insert(0, level)` 将层级添加到最顶部，以实现逆序的效果。

### 总结二叉树的层序遍历 II 是一个简单的问题，通过使用层序遍历（BFS）可以轻松解决。上述代码示例提供了 Java 和 Python语言的实现，分别使用队列和列表来存储每一层的节点值。