LeetCode 314. [Python] Binary Tree Vertical Order Traversal
原题链接
中等
作者:
徐辰潇
,
2021-01-13 07:02:22
,
所有人可见
,
阅读 304
# 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 verticalOrder(self, root: TreeNode) -> List[List[int]]:
#TC: O(total nodes)
#SC: O(total nodes)
#Just trasverse all nodes and save the corresponding locations in dict
Dict = collections.defaultdict(list)
Q = collections.deque([(root, 0)])
res = []
if not root:
return res
while(Q):
n = len(Q)
for _ in range(n):
node = Q[0][0]
loc = Q[0][1]
Dict[loc].append(node.val)
Q.popleft()
if node.left:
Q.append((node.left, loc-1))
if node.right:
Q.append((node.right, loc+1))
for key in sorted(Dict):
res.append(Dict[key])
return res