# LeetCode: 94. Binary Tree Inorder Traversal

## 题目¶

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

Example 1: ```Input: root = [1,null,2,3]
Output: [1,3,2]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = 
Output: 
```

Example 4: ```Input: root = [1,2]
Output: [2,1]
```

Example 5: ```Input: root = [1,null,2]
Output: [1,2]
```

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

• Recursive solution is trivial, could you do it iteratively?

## 解法¶

### 递归法实现中序遍历¶

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def inorderTraversal(self, root):
nodes = []
self._inorder(nodes, root)
return nodes

def _inorder(self, nodes, root):
if root is None:
return

self._inorder(nodes, root.left)
nodes.append(root.val)
self._inorder(nodes, root.right)
```

### stack 法实现中序遍历¶

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def inorderTraversal(self, root):
nodes = []
stack = []
curr = root

while curr is not None or stack:
while curr is not None:
stack.append(curr)
curr = curr.left

curr = stack.pop()
nodes.append(curr.val)
curr = curr.right

return nodes
```