# 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**
**iterative with stack**
**morris**
**morris2**

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

### 解法細節

:::success
:::

### Python Solution
recursive解

# 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)

# 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

# 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**

# 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`