用java写一下这道题,给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言,其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束,按列索引每一列上的所有结点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点,则按结点的值从小到大进行排序。 返回二叉树的 垂序遍历 序列。
时间: 2023-02-26 08:32:52 浏览: 71
可以考虑将二叉树的每个结点的行列坐标映射到一个一维的数组中,再对这个数组按照列从左到右,行从上到下,结点值从小到大进行排序,最后遍历排序后的数组,即可得到二叉树的垂序遍历序列。
Java 代码如下:
```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
Map<Integer, List<int[]>> map = new HashMap<>();
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
dfs(root, 0, 0, map, min, max);
List<List<Integer>> res = new ArrayList<>();
for (int i = min; i <= max; i++) {
List<int[]> list = map.get(i);
Collections.sort(list, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
List<Integer> col = new ArrayList<>();
for (int[] pair : list) {
col.add(pair[1]);
}
res.add(col);
}
return res;
}
private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> map, int min, int max) {
if (node == null) return;
min = Math.min(min, col);
max = Math.max(max, col);
List<int[]> list = map.getOrDefault(col, new ArrayList<>());
list.add(new int[] {row, node.val});
map.put(col, list);
dfs(node.left, row + 1, col - 1, map, min, max);
dfs(node.right, row + 1, col + 1, map, min, max);
}
}
```