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 1:
Input: [3,9,20,null,null,15,7]
3
/\
/ \
9 20
/\
/ \
15 7
Output:
[
[9],
[3,15],
[20],
[7]
]
Examples 2:
Input: [3,9,8,4,0,1,7]
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
Output:
[
[4],
[9],
[3,0,1],
[8],
[7]
]
Examples 3:
Input: [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 2
Output:
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
这道题非常有意思，如果想通了也很简单。给每个节点一个额外的level来记录在垂直方向上的层级，例如根节点层级为0，那么它的左子树节点层级为-1，右子树层级为1，左子树的左子树层级为-2，左子树的右子树层级为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):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
def traversal(root, dd, level):
if not root: return
dd[level].append(root.val)
traversal(root.left, dd, level - 1)
traversal(root.right, dd, level + 1)
dd = defaultdict(list)
traversal(root, dd, 0)
return list(map(lambda c: dd[c], sorted(dd.keys())))后来使用层序遍历，代码Accepted：
# 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):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
def traversal(root, dd, level): # 层序遍历
if not root: return
nodeStack = [(root, level)] # 使用额外的level记录层级
while nodeStack:
nextStack = []
for node, level in nodeStack:
dd[level].append(node.val)
if node.left:
nextStack.append((node.left, level - 1))
if node.right:
nextStack.append((node.right, level + 1))
nodeStack = nextStack
dd = defaultdict(list)
traversal(root, dd, 0)
return list(map(lambda c: dd[c], sorted(dd.keys()))) # 按key值进行排序，返回有序的结果