文章目录
- 987. Vertical Order Traversal of a Binary Tree二叉树的垂序遍历
- Tag
987. Vertical Order Traversal of a Binary Tree二叉树的垂序遍历
建议预备DFS,集合排序的知识,不然可能看的很慢。
一个二叉树根节点是root,要求垂序遍历 vertical order traversal,意思很简单,每个节点 都有2个属性【row,col】,row则是节点所处于的行,而col则是所处于的列, 如果当前节点的属性是(row,col),那么它的左右子节点的属性 就是 (row+1,col-1),(row+1,col+1),root的属性是(0,0).
垂序遍历的要求是 从最左的列开始直到最右边的列结束,然后按照每个列上,再按照row从上到下,如果相同的row,col有多个节点,就按值进行从小到大排序。
节点数量的规模范围[1,1000],节点值范围[0,1000]
问题很明显,先对每个节点进行编号,然后就可以排序了。
因为要求的排序与row,col,val相关。
即 先 按照col 从小到大排,再按照 row 从小到大排,最后 按照 val从小到大排。
可以先通过DFS,遍历tree,同时将节点的row,col和val,计入list。
然后对list 按照要求排序。
此时list已经是有序,但是结果要求将同一列的数据放在一起,所以最后还要将数据进行处理。
时间复杂度 O(NLogN),空间复杂度 O(N)
java"> Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
public List<List<Integer>> verticalTraversal(TreeNode root) {
map.put(root, new int[]{0, 0, root.val});
dfs(root);
List<int[]> list = new ArrayList<>(map.values());
Collections.sort(list, (a, b)->{
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];
});
int n = list.size();
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; ) {
int j = i;
List<Integer> tmp = new ArrayList<>();
while (j < n && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
ans.add(tmp);
i = j;
}
return ans;
}
void dfs(TreeNode root) {
if (root == null) return ;
int[] info = map.get(root);
int col = info[0], row = info[1], val = info[2];
if (root.left != null) {
map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
dfs(root.left);
}
if (root.right != null) {
map.put(root.right, new int[]{col + 1, row + 1, root.right.val});
dfs(root.right);
}
}
Tag
DFS
,树的遍历