# 二元樹的中序遍歷

中序遍歷的順序是 **left > middle > right**。
二元樹的中序遍歷是屬於**DFS 深度優先搜索**的一種

**詳細步驟:**

遞迴版本：

# 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 __init__(self):
        self.res = []

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root:
            if root.left:
                self.inorderTraversal(root.left)
            self.res.append(root.val)
            if root.right:
                self.inorderTraversal(root.right)
        return self.res

1. 建立棧和答案陣列，棧中不放根節點。
2. 建立節點指針。
3. 開始遍歷節點，棧和指針都為空時，即中止遍歷。
4. 檢查指針是否為空，如果不為空，就把當前節點放入棧中，等待指針為空的時候遍歷，並且把指針向左節點推進。
5. 如果指針為空，表示最左邊的節點已經走完了，因為棧先進先出的特性，所以現在在棧中的第一個節點就是指針的根節點，所以從棧裡拿出根節點，把根節點放入答案中，並且把指針指向根節點的右邊節點。
1.
迴圈版本：

# 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]:
        cur, stack, res = root, [], []
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                node = stack.pop()
                res.append(node.val)
                cur = node.right
        return res