当前位置： 面试刷题>> 二叉树的层序遍历(经典算法150题)
### 题目描述
给定一个二叉树，请按照从根节点开始，从上到下、从左到右的顺序（即层序遍历的顺序）打印出每个节点的值。每个节点都是一个包含整数值的节点。
**示例**：
假设我们有以下二叉树：
```
1
/ \
2 3
/ \
4 5
```
按照层序遍历的顺序，输出应该是 `[1, 2, 3, 4, 5]`。
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function levelOrder($root) {
$result = [];
if ($root === null) {
return $result;
}
$queue = new SplQueue();
$queue->enqueue($root);
while (!$queue->isEmpty()) {
$levelSize = $queue->count();
$currentLevel = [];
for ($i = 0; $i < $levelSize; $i++) {
$node = $queue->dequeue();
$currentLevel[] = $node->val;
if ($node->left !== null) {
$queue->enqueue($node->left);
}
if ($node->right !== null) {
$queue->enqueue($node->right);
}
}
$result[] = $currentLevel;
}
// Flatten the result if needed
return array_merge(...$result);
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$result = levelOrder($root);
print_r($result);
?>
```
### Python 示例代码
```python
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 = [root]
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.pop(0)
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.extend(current_level)
return result
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
result = levelOrder(root)
print(result)
```
### JavaScript 示例代码
```javascript
function TreeNode(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 currentLevel = [];
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result = result.concat(currentLevel);
}
return result;
}
// 示例用法
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
let result = levelOrder(root);
console.log(result);
```
在以上代码中，我们分别用 PHP、Python 和 JavaScript 实现了二叉树的层序遍历算法。这些示例代码均包含了树的定义、层序遍历函数以及示例用法，以帮助理解和测试算法的正确性。