# 94. Binary Tree Inorder Traversal
#### Difficulty: Easy
link: https://leetcode.com/problems/binary-tree-inorder-traversal/

### 1. Recursive method
#### $O(n)$ runtime, $O(n)$ space

##### 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]:
        result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                result.append(node.val)
                inorder(node.right)
        
        inorder(root)
        return result

### 2. Iterating method with Stack
#### $O(n)$ runtime, $O(n)$ space

##### 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]:
        stack, result = [], []
        node = root
        while True:
            while node is not None:
                stack.append(node)
                node = node.left
            if not stack:
                return result
            node = stack.pop()
            result.append(node.val)
            node = node.right

### 3. Morris Traversal
#### $O(n)$ runtime, $O(1)$ space

空間複雜度：O(1)，因為只用了兩個輔助指標。

時間複雜度：O(n)。證明時間複雜度為O(n)，最大的疑惑在於尋找中序遍歷下二叉樹中所有節點的前驅節點的時間複雜度是多少，即18-19行程式碼。

直覺上，認為它的複雜度是O(nlgn)，因為找單個節點的前驅節點與樹的高度有關。但事實上，尋找所有節點的前驅節點只需要O(n)時間。n個節點的二叉樹中一共有n-1條邊，整個過程中每條邊最多隻走2次，一次是為了定位到某個節點，另一次是為了尋找上面某個節點的前驅節點，如下圖所示，其中紅色是為了定位到某個節點，黑色線是為了找到前驅節點。所以複雜度為O(n)。

##### 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]:
        result = []
        node = root
        while node is not None:
            if node.left is None:
                result.append(node.val)
                node = node.right
            else:
                # Find the inorder predecessor of current node
                pred = node.left
                while pred.right is not None and pred.right is not node:
                    pred = pred.right
                
                # If the right child of inorder predecessor already points to
                # the current node, restore the original tree and update the 
                # current node to it's right child
                if pred.right is node:
                    result.append(node.val)
                    pred.right = None
                    node = node.right
                
                # Make current node as right child of its inorder predecessor
                else:
                    pred.right = node
                    node = node.left
        
        return result

Ref: https://www.796t.com/content/1545897069.html

###### tags: `leetcode`