中序遍历

递归写法、迭代写法（普通迭代写法、标记迭代写法）、莫里斯遍历（动态线索）

递归写法是最简单的写法，先序，中序，后序的代码都很相似，时间复杂度$O(n)$，空间复杂度$O(h)$此处省略。

迭代写法分为普通的迭代写法和标记迭代写法，普通的迭代写法的时间复杂度空间复杂度的常数更小，缺点是先序，中序，后序的代码差别很大可读性差。标记的迭代写法缺点是时间复杂度空间复杂度的常数更大，优点是写法和递归相似，先序，中序，后序的代码相似，可读性好。

//普通迭代.c
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    struct TreeNode* stack[100];
    int top = -1;
    int *ans = (int *)malloc(sizeof(int) * 100), idx = 0;
    struct TreeNode* cur = root;
    while(cur != NULL || top > -1){
        while(cur != NULL){
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top];
        ans[idx++] = cur->val;
        top--;
        cur = cur->right;
    }
    *returnSize = idx;
    return ans;
}
//标记迭代.py
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

莫里斯遍历时间复杂度常数比普通方法大，因为有些节点会遍历两次，但是空间复杂度是$O(1)$，Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 x）：

如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x=x.right。
如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。
如果 predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 x=x.left。
如果 predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将 predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 x=x.right。
重复上述操作，直至访问完整棵树。

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *ans = (int *)malloc(sizeof(int) * 100), idx = 0;
    struct TreeNode* cur = root;
    while(cur != NULL){
        if(cur->left == NULL){
            ans[idx++] = cur->val;
            cur = cur->right;
        } else {
            struct TreeNode* pre = cur->left;
            while(pre->right != NULL && pre->right != cur)pre = pre->right;
            if(pre->right == NULL){
                pre->right = cur;
                cur = cur->left;
            } else {
                ans[idx++] = cur->val;
                pre->right == NULL;
                cur = cur->right;
            }
        }
    }
    *returnSize = idx;
    return ans;
}

先序遍历、后序遍历

递归写法、迭代写法（标记迭代写法）