0987. Vertical Order Traversal of a Binary Tree¶
题目信息¶
- 题号:
0987
- 难度:
Hard
- 主题:
二叉树、行列坐标、垂直遍历
- 原题:
- 重点:
根位于
(row=0, col=0),左右孩子分别移动到下一行相邻列;结果按列、行、节点值三级升序组织
题目重述¶
给定二叉树根节点 root。规定根节点坐标为 (0, 0);位于 (row, col) 的节点,其左孩子坐标为 (row + 1, col - 1),右孩子坐标为 (row + 1, col + 1)。
请按列从最左到最右返回节点值。每一列内部先按行号从小到大排列;若多个节点具有相同的行号和列号,则按节点值从小到大排列。
树中节点数在 [1, 1000] 范围内,0 <= node.val <= 1000。
自建示例¶
同一列按深度排列:
输入:root = [3,1,4,null,2]
输出:[[1],[3,2],[4]]
解释:节点 1 位于列 -1;根 3 与节点 2 都位于列 0,但 3 的行号更小,因此排在 2 前;节点 4 位于列 1。
相同行列按节点值排序:
输入:root = [5,3,7,null,6,4]
输出:[[3],[5,4,6],[7]]
解释:节点 6 是左孩子 3 的右孩子,节点 4 是右孩子 7 的左孩子,二者都位于 row=2、col=0,因此按值 4、6 排列在根节点 5 之后。