314. Binary Tree Vertical Order Traversal
- Total Accepted: 13025
- Total Submissions: 38434
- Difficulty: Medium
- Contributors: Admin
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 from left to right.
Examples:
- Given binary tree
[3,9,20,null,null,15,7],3 /\ / \ 9 20 /\ / \ 15 7return 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 7return its vertical order traversal as:
[ [4], [9], [3,0,1], [8], [7] ]
- Given binary tree
[3,9,8,4,0,1,7,null,null,null,2,5](0’s right child is 2 and 1’s left child is 5),3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2return its vertical order traversal as:
[ [4], [9,5], [3,0,1], [8,2], [7] ]
Show Similar Problems
Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import defaultdict, deque
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
d = defaultdict(list)
l = deque([(root,0)])
while l:
n, v = l.popleft()
d[v].append(n.val)
if n.left:
l.append((n.left, v-1))
if n.right:
l.append((n.right, v+1))
res = []
for k in sorted(d.keys()):
res.append(d[k])
return res
Idea
Use BFS to traverse nodes. Since result must take O(N) space anyway, I don’t think there is much room to improve.