LC 0987 0314 [H] [M] Vertical Order Traversal of a Binary Tree, Binary Tree Vertical Order Traversal - ALawliet/algorithms GitHub Wiki
instead of levels and level lists, it's a levels and level dict
- think in BFS but adapted to cols by storing a tuple of the (node, offset)
- use a dict at levels
col=>[val]
and another dictcol=>[levels of vals]
- sort by node val in same col, then sort by col order instead of level-order
314 | Binary Tree Vertical Order Traversal | Medium
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return
col_to_levels = defaultdict(list)
# *** BFS ***
Q = deque([ (root, 0) ])
while Q:
col_to_level = defaultdict(list)
for _ in range(len(Q)):
node, c = Q.popleft()
col_to_level[c].append(node.val)
if node.left:
Q.append( (node.left, c-1) )
if node.right:
Q.append( (node.right, c+1) )
# *** BFS ***
# update the result after every BFS
# keep in that mind that you can have more than one node under the same col e.g. if \x/
for c, level in col_to_level.items():
# col_to_levels[c] += level # no need to sort so if two nodes have same col, smaller value comes first
col_to_levels[c].extend(level)
# return [col_to_levels[c] for c in sorted(col_to_levels)] # sort so they print left to right by col key instead of level-order
res = []
for c, level in sorted(col_to_levels.items()): # sort by col key
res.append(level)
return res
987 | Vertical Order Traversal of a Binary Tree | Hard
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root: return
col_to_levels = defaultdict(list)
Q = deque([ (root, 0) ])
while Q:
col_to_level = defaultdict(list)
for _ in range(len(Q)):
node, c = Q.popleft()
col_to_level[c].append(node.val)
if node.left:
Q.append( (node.left, c-1) )
if node.right:
Q.append( (node.right, c+1) )
for c, level in col_to_level.items():
col_to_levels[c].extend( sorted(level) ) # sort across the level too
res = []
for c, level in sorted(col_to_levels.items()): # sort by col keys
res.append(level)
return res
thinking in terms of Y = columns for all levels, y = columns for this level, x = column makes sense e.g. if we sorted(Y) where x = column is the key then we sort by column
Y = col_to_values_all_levels: col => values from all levels
y = col_to_values_cur_level: col => values from cur level
x = col
Nearly identical problems except how it is sorted across the level.
LC 314 If two nodes are in the same row and column, the order should be from left to right.
When two nodes are in the same position, the order is decided by their x coordinates (node from the left subtree comes first): node6 -> node3
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
if not root: return
levels = defaultdict(list)
Q = deque([(root, 0)])
while Q:
level = defaultdict(list) # cols in this level
for _ in range(len(Q)):
node, col = Q.popleft()
level[col] += node.val,
if node.left:
Q += (node.left, col-1),
if node.right:
Q += (node.right, col+1),
for col in level:
levels[col] += level[col] # do NOT sort values so if two nodes in same level have same col, just go left to right
return [levels[col] for col in sorted(levels)] # sort by col key so they print left to right by vertical-order instead of level-order
LC 987 If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
When two nodes are in the same position, the order is decided by their values (node with smaller value comes first): node3 -> node6
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
if not root: return
Y = defaultdict(list) # cols for all levels
Q = deque([(root, 0)])
while Q:
y = defaultdict(list) # cols for this current level
for _ in range(len(Q)):
node, x = Q.popleft()
y[x].append( node.val )
if node.left:
Q.append( (node.left, x-1) )
if node.right:
Q.append( (node.right, x+1) )
for x in y:
Y[x].append( sorted(y[x]) ) # sort values so if two nodes in same level have same col, smaller value comes first
return [Y[x] for x in sorted(Y)] # sort by col key so they print left to right by vertical-order instead of level-order
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
if not root: return
col_to_values_all_levels = defaultdict(list)
Q = deque([(root, 0)])
while Q:
col_to_values_cur_level = defaultdict(list)
for _ in range(len(Q)):
node, col = Q.popleft()
col_to_values_cur_level[col] += node.val,
if node.left:
Q += (node.left, col-1),
if node.right:
Q += (node.right, col+1),
for col in col_to_values_cur_level:
col_to_values_all_levels[col] += sorted(col_to_values_cur_level[col])
return [col_to_values_all_levels[col] for col in sorted(col_to_values_all_levels)]