Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be fromleft to right.
Example
Given binary tree{3,9,20,#,#,15,7}
3
/\
/ \
9 20
/\
/ \
15 7
Return its vertical order traversal as:
[[9],[3,15],[20],[7]]
Given binary tree{3,9,8,4,0,1,7}
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
Return its vertical order traversal as:
[[4],[9],[3,0,1],[8],[7]]
分析
如果是要求层顺序,使用bfs,如果要求root和l,r顺序,考虑pre in post
这题不知道为什么dfs不行,可能因为顺序?
因为要求行列都顺序,BFS天然保留了行顺序,只需要考虑COL顺序
但DFS需要加入额外的ROW追踪。
DFS
from collections import defaultdict
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
# Dictionary to store nodes by column and row
column_map = defaultdict(list)
min_col = max_col = 0
def dfs(node, row, col):
nonlocal min_col, max_col
if not node:
return
column_map[col].append((row, node.val))
min_col = min(min_col, col)
max_col = max(max_col, col)
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
dfs(root, 0, 0)
# Sort each column's entries by row, then by insertion order
result = []
for col in range(min_col, max_col + 1):
# Sort by row to maintain top-to-bottom order
column_map[col].sort(key=lambda x: x[0])
# Extract just the values
result.append([val for (row, val) in column_map[col]])
return result
dict可以用负数做Key和排序
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of tree
@return: the vertical order traversal
"""
def verticalOrder(self, root):
# write your code here
if not root:
return []
dict = collections.defaultdict(list)
q = collections.deque()
q.append((root,0))
while q:
size = len(q)
for i in range(size):
cur = q.popleft()
dict[cur[1]].append(cur[0].val)
if cur[0].left:
q.append((cur[0].left,cur[1]-1))
if cur[0].right:
q.append((cur[0].right,cur[1]+1))
ret = []
for key in sorted(dict.keys()):
ret.append(dict[key])
return ret