<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class TreeNode ( object ) : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . left = None <EOL> self . right = None <EOL> class Solution ( object ) : <EOL> def verticalOrder ( self , root ) : <EOL> """<STR_LIT>""" <EOL> l = self . leftmost ( root , <NUM_LIT:0> ) <EOL> r = self . rightmost ( root , <NUM_LIT:0> ) <EOL> ret = [ [ ] for _ in xrange ( r - l - <NUM_LIT:1> ) ] <EOL> self . bfs ( root , - l - <NUM_LIT:1> , ret ) <EOL> return ret <EOL> def bfs ( self , cur , col , ret ) : <EOL> q = [ ] <EOL> if cur : <EOL> q . append ( ( cur , col ) ) <EOL> while q : <EOL> l = len ( q ) <EOL> for i in xrange ( l ) : <EOL> v , c = q [ i ] <EOL> ret [ c ] . append ( v . val ) <EOL> if v . left : q . append ( ( v . left , c - <NUM_LIT:1> ) ) <EOL> if v . right : q . append ( ( v . right , c + <NUM_LIT:1> ) ) <EOL> q = q [ l : ] <EOL> def leftmost ( self , cur , l ) : <EOL> if not cur : return l <EOL> return min ( self . leftmost ( cur . left , l - <NUM_LIT:1> ) , self . leftmost ( cur . right , l + <NUM_LIT:1> ) ) <EOL> def rightmost ( self , cur , r ) : <EOL> if not cur : return r <EOL> return max ( self . rightmost ( cur . left , r - <NUM_LIT:1> ) , self . rightmost ( cur . right , r + <NUM_LIT:1> ) ) <EOL> def sidemost ( self , cur , p , f ) : <EOL> if not cur : return p <EOL> return f ( self . sidemost ( cur . left , p - <NUM_LIT:1> , f ) , self . sidemost ( cur . right , p + <NUM_LIT:1> , f ) ) </s>
