当前位置： 面试刷题>> 二叉树的锯齿形层序遍历(经典算法150题)
### 题目描述
给定一个二叉树，请实现一个函数，按照锯齿形（之字形）的顺序进行层序遍历。即第一层从左到右，第二层从右到左，第三层再从左到右，以此类推，返回遍历的结果。
**示例**：
给定二叉树:
```
3
/ \
9 20
/ \
15 7
```
按照锯齿形层序遍历的结果为：
```
[
[3],
[20, 9],
[15, 7]
]
```
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function zigzagLevelOrder($root) {
if ($root === null) {
return [];
}
$result = [];
$queue = new SplQueue();
$queue->enqueue([$root, 0]); // 节点和层级，层级用于判断方向
$level = 0;
while (!$queue->isEmpty()) {
[$node, $currentLevel] = $queue->dequeue();
if (!isset($result[$currentLevel])) {
$result[$currentLevel] = [];
}
// 根据层级决定是添加到数组开头还是末尾
if ($currentLevel % 2 === 0) {
array_push($result[$currentLevel], $node->val);
} else {
array_unshift($result[$currentLevel], $node->val);
}
if ($node->left !== null) {
$queue->enqueue([$node->left, $currentLevel + 1]);
}
if ($node->right !== null) {
$queue->enqueue([$node->right, $currentLevel + 1]);
}
}
// 移除空数组（如果树的高度是奇数，则最后一层可能为空）
return array_values(array_filter($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 = zigzagLevelOrder($root);
print_r($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 zigzagLevelOrder(root):
if not root:
return []
result = []
queue = deque([(root, 0)]) # 节点和层级
while queue:
node, level = queue.popleft()
if len(result) <= level:
result.append([])
# 根据层级决定是添加到列表开头还是末尾
if level % 2 == 0:
result[level].append(node.val)
else:
result[level].insert(0, node.val)
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
return result
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = zigzagLevelOrder(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 zigzagLevelOrder(root) {
if (!root) return [];
let result = [];
let queue = [[root, 0]]; // 节点和层级
while (queue.length > 0) {
let [node, level] = queue.shift();
if (!result[level]) {
result[level] = [];
}
// 根据层级决定是添加到数组开头还是末尾
if (level % 2 === 0) {
result[level].push(node.val);
} else {
result[level].unshift(node.val);
}
if (node.left) {
queue.push([node.left, level + 1]);
}
if (node.right) {
queue.push([node.right, level + 1]);
}
}
// 移除空数组
return result.filter(arr => arr.length > 0);
}
// 示例用法
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 = zigzagLevelOrder(root);
console.log(result);
```
以上代码均实现了二叉树的锯齿形层序遍历，并给出了示例用法。