DFS solution
# 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:
# time O(NlgN) space O(N)
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
self.d = collections.defaultdict(lambda: collections.defaultdict(list))
def dfs(node,x,y):
if not node:
return
# inorder
self.d[x][y].append(node.val)
if node.left:
dfs(node.left,x-1,y+1)
if node.right:
dfs(node.right,x+1,y+1) # trick to makesure decending by y coordinates
dfs(root,0,0)
res = []
for x in sorted(self.d):
val_list = []
for y in sorted(self.d[x]):
val_list.extend(sorted(val for val in self.d[x][y])) # to make sure when x,y is the same, smaller val place ahead
res.append(val_list)
return res
solution2 use queue
# 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
from collections import deque, defaultdict
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
#cornor case : root is None
if root is None:
return []
queue = deque() # assume root start position(x,y) is 0,0
queue.append((root,0,0))
d = defaultdict(list)
# d[0].append((0,root.val)) # use x as key
res = []
while queue:
for i in range(len(queue)):
node, x, y = queue.popleft()
d[x].append((y,node.val)) #d = {x:(y,node.val)}
if node.left:
queue.append((node.left,x-1,y-1))
if node.right:
queue.append((node.right,x+1,y-1))
for i in sorted(d.keys()):
level = [ y_val[1] for y_val in sorted(d[i], key = lambda y_val: (-y_val[0],y_val[1]))] #y_val = (y, node.val)
res.append(level)
return res