Binary Tree Vertical Order Traversal (987)

本文介绍了 LeetCode 第 987 题二叉树的垂序遍历。问题要求按列从上到下输出节点值，同列同行则按值排序。解决方案采用深度优先搜索（DFS）记录每个节点的行列坐标和值，将所有节点信息排序后按列分组输出。代码使用 C 语言实现，包含动态数组管理和自定义比较函数。

筑梦师发布于 2026/3/29更新于 2026/4/134 浏览

987. Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Example Image

Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.

Example 2:

Example Image

Input: root = [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column. 1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.

Example 3:

Example Image

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown 转 HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online

HTML 转 Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ typedef struct { int col; int row; int val; } Trip; typedef struct { Trip *a; int sz; int cap; } Vec; static void vec_push(Vec *v, int col, int row, int val) { if (v->sz == v->cap) { v->cap = (v->cap == 0) ? 64 : v->cap * 2; v->a = (Trip *)realloc(v->a, (size_t)v->cap * sizeof(Trip)); } v->a[v->sz++] = (Trip){col, row, val}; } static void dfs(struct TreeNode *node, int row, int col, Vec *v) { if (!node) return; vec_push(v, col, row, node->val); dfs(node->left, row + 1, col - 1, v); dfs(node->right, row + 1, col + 1, v); } static int cmp_trip(const void *p1, const void *p2) { const Trip *a = (const Trip *)p1; const Trip *b = (const Trip *)p2; if (a->col != b->col) return (a->col < b->col) ? -1 : 1; if (a->row != b->row) return (a->row < b->row) ? -1 : 1; if (a->val != b->val) return (a->val < b->val) ? -1 : 1; return 0; } /** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int **verticalTraversal(struct TreeNode *root, int *returnSize, int **returnColumnSizes) { *returnSize = 0; *returnColumnSizes = NULL; if (!root) return NULL; Vec v = {0}; dfs(root, 0, 0, &v); qsort(v.a, (size_t)v.sz, sizeof(Trip), cmp_trip); // Count distinct columns int cols = 0; for (int i = 0; i < v.sz;) { cols++; int c = v.a[i].col; while (i < v.sz && v.a[i].col == c) i++; } int **res = (int **)malloc((size_t)cols * sizeof(int *)); int *colSizes = (int *)malloc((size_t)cols * sizeof(int)); // Build result by grouping same column int idx = 0; for (int i = 0; i < v.sz;) { int c = v.a[i].col; int start = i; while (i < v.sz && v.a[i].col == c) i++; int len = i - start; colSizes[idx] = len; res[idx] = (int *)malloc((size_t)len * sizeof(int)); for (int k = 0; k < len; k++) { res[idx][k] = v.a[start + k].val; } idx++; } free(v.a); *returnSize = cols; *returnColumnSizes = colSizes; return res; }

Binary Tree Vertical Order Traversal (987)

987. Vertical Order Traversal of a Binary Tree

Example 1:

Example 2:

Example 3:

更多推荐文章

相关免费在线工具

Constraints:

Solution:

Ideas:

Code:

Binary Tree Vertical Order Traversal (987)

987. Vertical Order Traversal of a Binary Tree

Example 1:

Example 2:

Example 3:

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

Constraints:

Solution:

Ideas:

Code: