987. 二叉树的垂序遍历
题目描述
输入一棵二叉树的根节点 root，树用层序数组表示。
给每个节点一个坐标：根在 (0, 0)；位于 (row, col) 的节点，左孩子在 (row + 1, col - 1)，右孩子在 (row + 1, col + 1)。
按列号从小到大，为每一列生成一个列表，列表中依次放该列的节点值。同一列内按行号从小到大排；行号和列号都相同的节点，按节点值从小到大排。
返回由这些列表组成的二维数组。
示例 1
输入：root = [3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]]
解释：列 -1 只有 9，列 0 有 3 和 15，列 1 有 20，列 2 有 7。
示例 2
输入：root = [1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]]
解释：列 0 中 1 在第 0 行最先；5 和 6 都在 (2, 0)，按值排成 5、6。
示例 3
输入：root = [1,2,3,4,6,5,7] 输出：[[4],[2],[1,5,6],[3],[7]]
解释：与示例 2 相比只交换了 5 和 6 的位置，二者坐标相同，结果不变。
数据范围
- 节点数在
[1, 1000]范围内。 0 <= Node.val <= 1000
解题思路
排序规则有三层：列、行、值。先用一次 DFS 给每个节点算出坐标，记成三元组 (col, row, val)。三元组按字典序排序后，正好就是题目要求的输出顺序。最后顺序扫描，列号变化时开一个新分组。
为什么正确
DFS 时每个节点的 (row, col) 只由父节点决定：row 加 1，向左 col 减 1，向右 col 加 1。排序后同一列的三元组连续出现。
复杂度分析
时间 O(n log n)（排序），空间 O(n)。
易错点
同一行同一列的节点要按值排序，不能按遍历顺序。只按列分组、用 BFS 顺序输出，会在这种情况下出错。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
nodes = []
def dfs(node, row, col):
if not node:
return
nodes.append((col, row, node.val))
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
dfs(root, 0, 0)
nodes.sort()
ans = []
last = None
for col, row, val in nodes:
if col != last:
ans.append([])
last = col
ans[-1].append(val)
return ansclass Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<int[]> nodes = new ArrayList<>();
dfs(root, 0, 0, nodes);
nodes.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
List<List<Integer>> ans = new ArrayList<>();
Integer last = null;
for (int[] t : nodes) {
if (last == null || t[0] != last) {
ans.add(new ArrayList<>());
last = t[0];
}
ans.get(ans.size() - 1).add(t[2]);
}
return ans;
}
void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
if (node == null) {
return;
}
nodes.add(new int[]{col, row, node.val});
dfs(node.left, row + 1, col - 1, nodes);
dfs(node.right, row + 1, col + 1, nodes);
}
}class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<tuple<int, int, int>> nodes;
function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {
if (!node) {
return;
}
nodes.emplace_back(col, row, node->val);
dfs(node->left, row + 1, col - 1);
dfs(node->right, row + 1, col + 1);
};
dfs(root, 0, 0);
sort(nodes.begin(), nodes.end());
vector<vector<int>> ans;
int last = INT_MIN;
for (auto& [col, row, val] : nodes) {
if (col != last) {
ans.push_back({});
last = col;
}
ans.back().push_back(val);
}
return ans;
}
};func verticalTraversal(root *TreeNode) [][]int {
nodes := [][3]int{}
var dfs func(node *TreeNode, row, col int)
dfs = func(node *TreeNode, row, col int) {
if node == nil {
return
}
nodes = append(nodes, [3]int{col, row, node.Val})
dfs(node.Left, row+1, col-1)
dfs(node.Right, row+1, col+1)
}
dfs(root, 0, 0)
sort.Slice(nodes, func(i, j int) bool {
a, b := nodes[i], nodes[j]
if a[0] != b[0] {
return a[0] < b[0]
}
if a[1] != b[1] {
return a[1] < b[1]
}
return a[2] < b[2]
})
ans := [][]int{}
last := math.MinInt32
for _, t := range nodes {
if t[0] != last {
ans = append(ans, []int{})
last = t[0]
}
ans[len(ans)-1] = append(ans[len(ans)-1], t[2])
}
return ans
}var verticalTraversal = function(root) {
const nodes = [];
const dfs = (node, row, col) => {
if (!node) {
return;
}
nodes.push([col, row, node.val]);
dfs(node.left, row + 1, col - 1);
dfs(node.right, row + 1, col + 1);
};
dfs(root, 0, 0);
nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
const ans = [];
let last = null;
for (const [col, row, val] of nodes) {
if (col !== last) {
ans.push([]);
last = col;
}
ans[ans.length - 1].push(val);
}
return ans;
};function verticalTraversal(root: TreeNode | null): number[][] {
const nodes: number[][] = [];
const dfs = (node: TreeNode | null, row: number, col: number): void => {
if (!node) {
return;
}
nodes.push([col, row, node.val]);
dfs(node.left, row + 1, col - 1);
dfs(node.right, row + 1, col + 1);
};
dfs(root, 0, 0);
nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
const ans: number[][] = [];
let last: number | null = null;
for (const [col, row, val] of nodes) {
if (col !== last) {
ans.push([]);
last = col;
}
ans[ans.length - 1].push(val);
}
return ans;
}