Module Expr Str Assign NameStore Str ClassDef bases NameLoad body FunctionDef arguments args NameParam NameParam defaults body Assign AttributeStore NameLoad attr NameLoad Assign AttributeStore NameLoad attr NameLoad Assign AttributeStore NameLoad attr NameLoad decorator_list decorator_list ClassDef bases NameLoad body FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore ListLoad Assign NameStore NameLoad While NameLoad body If UnaryOpNot AttributeLoad NameLoad attr body Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr orelse Assign NameStore AttributeLoad NameLoad attr While BoolOpAnd AttributeLoad NameLoad attr CompareNotEq AttributeLoad NameLoad attr NameLoad body Assign NameStore AttributeLoad NameLoad attr If UnaryOpNot AttributeLoad NameLoad attr body Assign AttributeStore NameLoad attr NameLoad Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr Assign NameStore AttributeLoad NameLoad attr orelse Assign AttributeStore NameLoad attr NameLoad Assign NameStore AttributeLoad NameLoad attr Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assign NameStore ListLoad Expr Call AttributeLoad NameLoad attr NameLoad NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body If UnaryOpNot NameLoad body Return Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr NameLoad Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str If UnaryOpNot NameLoad body Return Assign NameStore ListLoad NameLoad While NameLoad body Assign NameStore Call AttributeLoad NameLoad attr Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr If AttributeLoad NameLoad attr body Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr If AttributeLoad NameLoad attr body Expr Call AttributeLoad NameLoad attr AttributeLoad NameLoad attr decorator_list decorator_list If CompareEq NameLoad Str body Assign NameStore Call NameLoad Num Assign AttributeStore NameLoad attr Call NameLoad Num Print Call AttributeLoad Call NameLoad attr NameLoad
N/A N/A 
Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
         2
    /
   3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively? - see preTraverse_itr
 N/A __author__ Danyang TreeNode N/A object N/A __init__ N/A N/A self x N/A N/A N/A N/A self val x N/A N/A self left None N/A N/A self right None N/A N/A Solution N/A object N/A preorderTraversal N/A N/A self root N/A N/A N/A Morris N/A ret N/A N/A cur root N/A cur N/A N/A N/A N/A cur left N/A N/A N/A N/A ret append N/A cur val N/A cur N/A cur right N/A N/A pre N/A cur left N/A N/A N/A pre right N/A N/A pre right cur N/A N/A pre N/A pre right N/A N/A N/A pre right N/A N/A N/A pre right cur N/A N/A N/A ret append N/A cur val N/A cur N/A cur left N/A N/A N/A pre right None N/A cur N/A cur right N/A ret N/A preorderTraversal_memory N/A N/A self root N/A N/A N/A 
        dfs
        :param root:
        :return:
         N/A lst N/A N/A N/A N/A self preTraverse_itr root lst N/A lst N/A preTraverse N/A N/A self node lst N/A N/A N/A N/A node N/A N/A N/A N/A N/A lst append N/A node val N/A N/A N/A self preTraverse N/A node left lst N/A N/A N/A self preTraverse N/A node right lst N/A preTraverse_itr N/A N/A self root lst N/A N/A N/A 
        stack = [R, L, cur]

        Pretty simple using stack
        double stacks

        :param root:
        :param lst:
        :return:
         N/A N/A root N/A N/A N/A stk N/A root N/A stk N/A N/A node N/A N/A stk pop N/A N/A N/A lst append N/A node val N/A N/A node right N/A N/A N/A N/A stk append N/A node right N/A N/A node left N/A N/A N/A N/A stk append N/A node left N/A N/A N/A N/A __name__ __main__ N/A N/A t1 N/A TreeNode 1 N/A N/A t1 left N/A TreeNode 2 N/A N/A N/A N/A Solution preorderTraversal t1