# 94. Binary Tree Inorder Traversal

## 刷题内容

• https://leetcode.com/problems/binary-tree-inorder-traversal


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?


## 解题方案

class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
if root.left:
res.extend(self.inorderTraversal(root.left))
res.append(root.val)
if root.right:
res.extend(self.inorderTraversal(root.right))
return res


class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
res = []
self.inorder(root,res)
return res

def inorder(self,root,res):
if root == None:
return
self.inorder(root.left,res)
res.append(root.val)
self.inorder(root.right,res)


class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res

stack = []
node = root
while node or (len(stack) > 0):
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
res.append(node.val)
node = node.right
return res