# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import defaultdict
from queue import deque
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
dq = deque([(0, root)])
lookup = defaultdict(list)
while dq:
idx, node = dq.popleft()
lookup[idx].append(node.val)
if node.left:
dq.append((idx-1, node.left))
if node.right:
dq.append((idx+1, node.right))
return [val for idx, val in sorted(lookup.items(), key=lambda x: x[0])]# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import defaultdict
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
level = [(0, root)]
lookup = defaultdict(list)
while level:
tmpLevel = []
for idx, node in level:
lookup[idx].append(node.val)
if node.left:
tmpLevel.append((idx-1, node.left))
if node.right:
tmpLevel.append((idx+1, node.right))
level = tmpLevel
ret = []
for idx in sorted(lookup.keys()):
ret.append(lookup[idx])
return ret