<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 preorderTraversal ( self , root ) : <EOL> """<STR_LIT>""" <EOL> ret = [ ] <EOL> cur = root <EOL> while cur : <EOL> if not cur . left : <EOL> ret . append ( cur . val ) <EOL> cur = cur . right <EOL> else : <EOL> pre = cur . left <EOL> while pre . right and pre . right != cur : <EOL> pre = pre . right <EOL> if not pre . right : <EOL> pre . right = cur <EOL> ret . append ( cur . val ) <EOL> cur = cur . left <EOL> else : <EOL> pre . right = None <EOL> cur = cur . right <EOL> return ret <EOL> def preorderTraversal_memory ( self , root ) : <EOL> """<STR_LIT>""" <EOL> lst = [ ] <EOL> self . preTraverse_itr ( root , lst ) <EOL> return lst <EOL> def preTraverse ( self , node , lst ) : <EOL> if not node : <EOL> return <EOL> lst . append ( node . val ) <EOL> self . preTraverse ( node . left , lst ) <EOL> self . preTraverse ( node . right , lst ) <EOL> def preTraverse_itr ( self , root , lst ) : <EOL> """<STR_LIT>""" <EOL> if not root : <EOL> return <EOL> stk = [ root ] <EOL> while stk : <EOL> node = stk . pop ( ) <EOL> lst . append ( node . val ) <EOL> if node . right : <EOL> stk . append ( node . right ) <EOL> if node . left : <EOL> stk . append ( node . left ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> t1 = TreeNode ( <NUM_LIT:1> ) <EOL> t1 . left = TreeNode ( <NUM_LIT:2> ) <EOL> print Solution ( ) . preorderTraversal ( t1 ) </s>
