Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit1f2e4bd

Browse files
author
night
committed
vertival order traversal
1 parent8c5f0c0 commit1f2e4bd

File tree

4 files changed

+106
-0
lines changed

4 files changed

+106
-0
lines changed

‎note/314/README.md

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#[Binary Tree Vertical Order Traversal][title]
2+
3+
##Description
4+
5+
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).
6+
7+
If two nodes are in the same row and column, the order should be from left to right.
8+
9+
10+
**Example:**
11+
12+
![image](img.png)
13+
14+
```
15+
Input: root = [3,9,20,null,null,15,7]
16+
Output: [[9],[3,15],[20],[7]]
17+
```
18+
19+
![image](img_1.png)
20+
21+
```
22+
Input: root = [3,9,8,4,0,1,7]
23+
Output: [[4],[9],[3,0,1],[8],[7]]
24+
```
25+
26+
##Solution
27+
BFS 遍历树, 再用一个 hashMap 存储当前 column 和 value 的对应关系。
28+
每遍历到一个 node 时更新到 map 中,针对下一层的 left, right。
29+
分别将 (left, col - 1) 和 (right, col + 1)的 pair 加入到 queue 中。
30+
同时在遍历过程中记录最左侧的 column 和 最右侧的 column, 避免了访问结束后对 map 进行排序的耗时。
31+
32+
T: O(N)
33+
S: O(N)
34+
35+
```kotlin
36+
classSolution {
37+
funverticalOrder(root:TreeNode?):List<List<Int>> {
38+
root?:return emptyList()
39+
val queue=ArrayDeque<Pair<TreeNode,Int>>()
40+
val columnMap= mutableMapOf<Int,MutableList<Int>>()
41+
val result= mutableListOf<List<Int>>()
42+
queue.add(root to0)
43+
var minColumn=Int.MAX_VALUE
44+
var maxColumn=Int.MIN_VALUE
45+
while (queue.isNotEmpty()) {
46+
val (node, col)= queue.removeFirst()
47+
columnMap.getOrPut(col) {mutableListOf() }.add(node.`val`)
48+
node.left?.apply { queue.add(this to col-1) }
49+
node.right?.apply { queue.add(this to col+1) }
50+
minColumn= min(minColumn, col)
51+
maxColumn= max(maxColumn, col)
52+
}
53+
54+
for (iin minColumn..maxColumn) {
55+
result.add(columnMap.getValue(i))
56+
}
57+
return result
58+
}
59+
}
60+
61+
```
62+
63+
64+
##结语
65+
66+
如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:[awesome-java-leetcode][ajl]
67+
68+
69+
[title]:https://leetcode.cn/problems/binary-tree-vertical-order-traversal/description/?company_slug=facebook
70+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎note/314/img.png

38.6 KB
Loading

‎note/314/img_1.png

47.7 KB
Loading
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packagecom.blankj.medium._314
2+
3+
importcom.blankj.ext.print
4+
importcom.blankj.structure.TreeNode
5+
importkotlin.math.max
6+
importkotlin.math.min
7+
8+
classSolution {
9+
funverticalOrder(root:TreeNode?):List<List<Int>> {
10+
root?:return emptyList()
11+
val queue=ArrayDeque<Pair<TreeNode,Int>>()
12+
val columnMap= mutableMapOf<Int,MutableList<Int>>()
13+
val result= mutableListOf<List<Int>>()
14+
queue.add(root to0)
15+
var minColumn=Int.MAX_VALUE
16+
var maxColumn=Int.MIN_VALUE
17+
while (queue.isNotEmpty()) {
18+
val (node, col)= queue.removeFirst()
19+
columnMap.getOrPut(col) {mutableListOf() }.add(node.`val`)
20+
node.left?.apply { queue.add(this to col-1) }
21+
node.right?.apply { queue.add(this to col+1) }
22+
minColumn= min(minColumn, col)
23+
maxColumn= max(maxColumn, col)
24+
}
25+
26+
for (iin minColumn..maxColumn) {
27+
result.add(columnMap.getValue(i))
28+
}
29+
return result
30+
}
31+
}
32+
33+
funmain() {
34+
Solution().verticalOrder(TreeNode.createTestData("[3,9,20,null,null,15,7]")).print()
35+
Solution().verticalOrder(TreeNode.createTestData("[3,9,8,4,0,1,7,null,null,null,2,5]")).print()
36+
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp