当前位置： 面试刷题>> 二叉树的层次遍历 (经典算法题500道)
### 题目描述补充
**题目**： 实现二叉树的层次遍历（也称为广度优先遍历）。给定一个二叉树，按照从上到下、从左到右的顺序遍历二叉树的节点，并返回遍历的结果。
**示例**：
给定二叉树：
```
3
/ \
9 20
/ \
15 7
```
应该返回遍历的结果为：`[3, 9, 20, 15, 7]`。
### 示例代码
#### 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;
}
// 如果题目要求的是一维数组而非二维（每层作为子数组），则进行合并
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);
print_r(levelOrder($root));
?>
```
#### 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.extend(level_nodes) # 如果需要一维数组
# 如果需要二维数组，则取消上一行，并取消注释下一行
# result.append(level_nodes)
return result
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(levelOrder(root))
```
#### 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 [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const levelNodes = [];
for (let i = 0; i < levelSize; i++) {
const 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.push(levelNodes);
}
return result;
}
// 示例用法
const 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);
console.log(levelOrder(root));
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法题解、数据结构深入讲解等，欢迎大家访问学习。