0987. Vertical Order Traversal of a Binary Tree

题目信息

题号:

0987

难度:

Hard

主题:

二叉树、行列坐标、垂直遍历

原题:

LeetCode 0987

重点:

根位于 (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 之后。