94.py

'''
 Given a binary tree, return the inorder traversal of its nodes' values.

 Example:

 Input: [1,null,2,3]
 1
\
 2
 /
 3

 Output: [1,3,2]

 Follow up: Recursive solution is trivial, could you do it iteratively?
'''

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

classSolution(object):
definorderTraversal(self, root):
"""
 :type root: TreeNode
 :rtype: List[int]
 """
ifnotroot:
return []

stack, result= [root], []
whilestack:
ifroot.left:
stack.append(root.left)
root=root.left
else:
node=stack.pop()
result.append(node.val)

ifnode.right:
stack.append(node.right)
root=node.right
returnresult