当前位置： 面试刷题>> 二叉树层次遍历(经典算法150题)
### 题目描述
**题目：二叉树的层次遍历**
给定一个二叉树，请你按从根节点开始从上到下的顺序，逐层遍历二叉树的所有节点，同一层的节点从左到右依次输出。
**示例**：
给定如下二叉树：
```
3
/ \
9 20
/ \
15 7
```
其层次遍历的结果为：
```
[3, 9, 20, 15, 7]
```
### 解题思路
层次遍历通常使用队列（Queue）来实现。首先将根节点入队，然后不断循环进行以下操作：
1. 从队列中取出一个节点，访问它（此处为加入结果列表）。
2. 如果该节点有左子节点，则将左子节点入队。
3. 如果该节点有右子节点，则将右子节点入队。
4. 重复步骤1至3，直到队列为空。
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function levelOrder($root) {
if ($root === null) {
return [];
}
$result = [];
$queue = new SplQueue();
$queue->enqueue($root);
while (!$queue->isEmpty()) {
$levelSize = $queue->count();
$levelNodes = [];
for ($i = 0; $i < $levelSize; $i++) {
$node = $queue->dequeue();
$levelNodes[] = $node->val;
if ($node->left !== null) {
$queue->enqueue($node->left);
}
if ($node->right !== null) {
$queue->enqueue($node->right);
}
}
$result[] = $levelNodes;
}
// 如果题目要求输出扁平化结果，则合并$result
return array_merge(...$result);
}
// 示例用法
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);
$result = levelOrder($root);
print_r($result);
?>
```
注意：上述 PHP 示例中，我假设了题目要求输出扁平化后的数组，如果题目要求每层作为一个子数组返回，则可以去掉最后一行的 `array_merge(...$result)`，直接返回 `$result`。
### Python 示例代码
```python
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
# 如果题目要求输出扁平化结果，则合并result
return [item for sublist in result for item in sublist]
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = levelOrder(root)
print(result)
```
### JavaScript 示例代码
```javascript
class TreeNode {
constructor(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
function levelOrder(root) {
if (!root) {
return [];
}
let result = [];
let queue = [root];
while (queue.length > 0) {
let levelSize = queue.length;
let levelNodes = [];
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
levelNodes.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
result.push(levelNodes);
}
// 如果题目要求输出扁平化结果，则合并result
return result.reduce((acc, val) => acc.concat(val), []);
}
// 示例用法
let root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
let result = levelOrder(root);
console.log(result);
```
在以上三个示例中，我都考虑了如果题目要求输出扁平化数组的情况，并给出了相应的转换方法。如果题目没有这样的要求，直接返回 `result` 即可，其中 `result` 包含了每一层的节点值作为子数组。