当前位置： 面试刷题>> 二叉树垂直遍历 (经典算法题500道)
### 题目描述补充
**题目：二叉树垂直遍历**
给定一棵二叉树，请按照从上到下、从左到右的顺序进行垂直遍历（也称为层次遍历，但考虑了节点的垂直位置）。对于同一垂直线上的节点，我们按照它们出现的顺序进行排序。如果两个节点在同一垂直线上，但是位于不同的水平线上，则位于较低水平线上的节点应该出现在结果列表中靠后的位置。
**示例**：
给定二叉树如下：
```
3
/ \
9 20
/ \
15 7
```
垂直遍历的结果应为：
```
[[9], [3, 15], [20], [7]]
```
解释：
- 节点 9 在最左边，位于垂直线 0 上。
- 节点 3 和 15 在中间，位于垂直线 1 上，3 在 15 的上方，所以 3 先出现。
- 节点 20 在右边，位于垂直线 2 上。
- 节点 7 在最右边，位于垂直线 3 上。
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function verticalOrder($root) {
if ($root === null) {
return [];
}
$map = [];
$queue = new SplQueue();
$queue->enqueue([$root, 0]); // [$node, x-coordinate]
while (!$queue->isEmpty()) {
[$node, $x] = $queue->dequeue();
if (!isset($map[$x])) {
$map[$x] = [];
}
$map[$x][] = $node->val;
if ($node->left !== null) {
$queue->enqueue([$node->left, $x - 1]);
}
if ($node->right !== null) {
$queue->enqueue([$node->right, $x + 1]);
}
}
ksort($map); // Sort by keys (x-coordinates)
return array_values($map);
}
// 示例用法
$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 = verticalOrder($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 verticalOrder(root):
if not root:
return []
map = {}
queue = [(root, 0)] # (node, x-coordinate)
while queue:
node, x = queue.pop(0)
if x not in map:
map[x] = []
map[x].append(node.val)
if node.left:
queue.append((node.left, x - 1))
if node.right:
queue.append((node.right, x + 1))
# Sort by keys (x-coordinates)
return [map[x] for x in sorted(map.keys())]
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = verticalOrder(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 verticalOrder(root) {
if (!root) return [];
const map = new Map();
const queue = [[root, 0]]; // [node, x-coordinate]
while (queue.length > 0) {
const [node, x] = queue.shift();
if (!map.has(x)) {
map.set(x, []);
}
map.get(x).push(node.val);
if (node.left) {
queue.push([node.left, x - 1]);
}
if (node.right) {
queue.push([node.right, x + 1]);
}
}
// Sort by keys (x-coordinates)
const keys = Array.from(map.keys()).sort((a, b) => a - b);
return keys.map(key => map.get(key));
}
// 示例用法
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);
const result = verticalOrder(root);
console.log(result);
```
码小课网站中有更多相关内容分享给大家学习，涵盖了数据结构与算法的各种知识点，包括但不限于二叉树的遍历、搜索、排序等算法，以及它们在不同编程语言中的实现方式。