---
# System prepended metadata

title: Leetcode ---  94. Binary Tree Inorder Traversal
tags: [leetcode, easy, tree, homework]

---

# Leetcode ---  94. Binary Tree Inorder Traversal


## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) 
### Description:
Given the root of a binary tree, return the inorder traversal of its nodes' values.

:::info


:::


**recursive**
![](https://i.imgur.com/5Q3ivP4.png)
**iterative with stack**
![](https://i.imgur.com/uaFoVa4.png)
**morris**
![](https://i.imgur.com/mt7ZIXG.png)
**morris2**
![](https://i.imgur.com/CMiwJFt.png)


### 解法條列
1.  recursive解 O(n) **O(log n)?**
2.  iterative解 O(n) O(n)
3.  morris解 O(n) O(1)

### 解法細節

:::success
:::


### Python Solution
recursive解
```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: Optional[TreeNode]) -> List[int]:
        ans = []
        def inorderTraversal_helper(node):
            if(node):
                inorderTraversal_helper(node.left)
                ans.append(node.val)
                inorderTraversal_helper(node.right)
        inorderTraversal_helper(root)
        return ans
```


---

iterative解 (with stack)
```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: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        node = root
        while(node or stack):
            while(node):
                stack.append(node)
                node = node.left
            node = stack.pop()
            ans.append(node.val)
            node = node.right
        return ans
                
```
---
Morris
```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: Optional[TreeNode]) -> List[int]:
        ans = []
        while(root):
            if(root.left):
                node = root.left
                while(node.right and node.right != root):
                    node = node.right

                if(node.right == root):
                    node.right = None
                    ans.append(root.val)
                    root = root.right
                    continue

                node.right = root
                root = root.left
            else:
                ans.append(root.val)
                root = root.right
        return ans          
                

```

---

**Morris2**
```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: Optional[TreeNode]) -> List[int]:
        ans = []
        while(root):
            if(root.left):
                node = root.left
                while(node.right and node.right != root):
                    node = node.right
                if(node.right == root):
                    node.right = None
                    ans.append(root.val)
                    root = root.right
                else:
                    node.right = root
                    root = root.left
            else:
                ans.append(root.val)
                root = root.right
        return ans          
                
```

---


---



###### tags: `leetcode` `tree` `easy`  `homework`