<s> class TreeNode : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . left = None <EOL> self . right = None <EOL> class Solution : <EOL> def inorderTraversal ( self , root ) : <EOL> result , prev , cur = [ ] , None , root <EOL> while cur : <EOL> if cur . left is None : <EOL> result . append ( cur . val ) <EOL> prev = cur <EOL> cur = cur . right <EOL> else : <EOL> node = cur . left <EOL> while node . right and node . right != cur : <EOL> node = node . right <EOL> if node . right is None : <EOL> node . right = cur <EOL> cur = cur . left <EOL> else : <EOL> result . append ( cur . val ) <EOL> node . right = None <EOL> prev = cur <EOL> cur = cur . right <EOL> return result <EOL> class Solution2 : <EOL> def inorderTraversal ( self , root ) : <EOL> result , stack , current , last_traversed = [ ] , [ ] , root , None <EOL> while stack or current : <EOL> if current : <EOL> stack . append ( current ) <EOL> current = current . left <EOL> else : <EOL> parent = stack [ - <NUM_LIT:1> ] <EOL> if parent . right in ( None , last_traversed ) : <EOL> if parent . right is None : <EOL> result . append ( parent . val ) <EOL> last_traversed = stack . pop ( ) <EOL> else : <EOL> result . append ( parent . val ) <EOL> current = parent . right <EOL> return result <EOL> class Solution3 : <EOL> def inorderTraversal ( self , root ) : <EOL> result , stack , current = [ ] , [ ] , root <EOL> while stack or current : <EOL> if current : <EOL> stack . append ( current ) <EOL> current = current . left <EOL> else : <EOL> current = stack . pop ( ) <EOL> result . append ( current . val ) <EOL> current = current . right <EOL> return result <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> root = TreeNode ( <NUM_LIT:1> ) <EOL> root . right = TreeNode ( <NUM_LIT:2> ) <EOL> root . right . left = TreeNode ( <NUM_LIT:3> ) <EOL> result = Solution ( ) . inorderTraversal ( root ) <EOL> print result </s>
