题目描述补充

题目：二叉树垂直遍历

给定一棵二叉树，请按照从上到下、从左到右的顺序进行垂直遍历（也称为层次遍历，但考虑了节点的垂直位置）。对于同一垂直线上的节点，我们按照它们出现的顺序进行排序。如果两个节点在同一垂直线上，但是位于不同的水平线上，则位于较低水平线上的节点应该出现在结果列表中靠后的位置。

示例：

给定二叉树如下：

    3
   / \
  9  20
    /  \
   15   7

垂直遍历的结果应为：

[[9], [3, 15], [20], [7]]

解释：

• 节点 9 在最左边，位于垂直线 0 上。
• 节点 3 和 15 在中间，位于垂直线 1 上，3 在 15 的上方，所以 3 先出现。
• 节点 20 在右边，位于垂直线 2 上。
• 节点 7 在最右边，位于垂直线 3 上。

PHP 示例代码

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->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 示例代码

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 示例代码

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);

码小课网站中有更多相关内容分享给大家学习，涵盖了数据结构与算法的各种知识点，包括但不限于二叉树的遍历、搜索、排序等算法，以及它们在不同编程语言中的实现方式。