# 94. Binary Tree Inorder Traversal

{% embed url="<https://leetcode.com/problems/binary-tree-inorder-traversal/>" %}

`DFS inorder`，没想到`iteratively`写起来还挺麻烦，需要先遍历到底再开始记录值。`recursively`就没啥区别了，可以看Q144的`preorder`对比。

{% content-ref url="144.-binary-tree-preorder-traversal" %}
[144.-binary-tree-preorder-traversal](https://xuqiangwen1994.gitbook.io/practice/144.-binary-tree-preorder-traversal)
{% endcontent-ref %}

{% tabs %}
{% tab title="iteratively" %}

```python
# 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: TreeNode) -> List[int]:
        if not root: return []
        
        stack = collections.deque([])
        res = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
            
        return res
```

{% endtab %}

{% tab title="recursively" %}

```python
# 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: TreeNode) -> List[int]:
        res = []
        
        def inorder(node, res):
            if not node: return
            inorder(node.left, res)
            res.append(node.val)
            inorder(node.right, res)
        
        inorder(root, res)
        return res
```

{% endtab %}
{% endtabs %}
