二叉树的中序遍历

描述
二叉树的中序遍历是一种遍历顺序：先访问左子树，再访问根节点，最后访问右子树。对于二叉搜索树（BST），中序遍历的结果是升序排列的节点值。该遍历是面试中基础且高频的考点，通常要求递归和迭代两种解法。

步骤 1：递归解法
递归解法直接遵循中序遍历的定义：

1. 递归遍历左子树；
2. 访问根节点；
3. 递归遍历右子树。

代码框架（以 C++ 为例）：

void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderTraversal(root->left, result);  // 先递归左子树
    result.push_back(root->val);           // 访问根节点
    inorderTraversal(root->right, result); // 最后递归右子树
}

关键点：

• 递归终止条件为节点为空（nullptr）；
• 注意 result 需通过引用传递以保存结果。

步骤 2：迭代解法（使用栈模拟递归）
递归的本质是函数调用栈，迭代法通过显式栈模拟这一过程：

1. 从根节点开始，将所有左子节点入栈，直到最左侧节点；
2. 弹出栈顶节点（当前最左节点），访问该节点；
3. 转向该节点的右子树，重复步骤 1。

代码实现：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    
    while (cur != nullptr || !stk.empty()) {
        // 遍历到最左侧节点，路径上的节点全部入栈
        while (cur != nullptr) {
            stk.push(cur);
            cur = cur->left;
        }
        // 弹出栈顶并访问
        cur = stk.top();
        stk.pop();
        result.push_back(cur->val);
        // 转向右子树
        cur = cur->right;
    }
    return result;
}

关键点：

• 外层循环条件为 cur 非空或栈非空，确保遍历完整；
• 内层循环负责向左深入，外层循环处理右子树。

步骤 3：Morris 中序遍历（空间复杂度 O(1)）
Morris 遍历利用叶子节点的空指针临时保存关系，避免使用栈：

1. 若当前节点 cur 无左子树，直接访问 cur 并转向右子树；
2. 若 cur 有左子树，找到左子树的最右节点（即 cur 的前驱节点）：
   • 若前驱节点的右指针为空，将其指向 cur（建立临时链接），然后 cur 向左移动；
   • 若前驱节点的右指针指向 cur（说明已访问过左子树），则断开链接，访问 cur 并转向右子树。

代码实现：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    TreeNode* cur = root;
    
    while (cur != nullptr) {
        if (cur->left == nullptr) {
            // 无左子树，访问当前节点并转向右子树
            result.push_back(cur->val);
            cur = cur->right;
        } else {
            // 找到左子树的最右节点（前驱节点）
            TreeNode* prev = cur->left;
            while (prev->right != nullptr && prev->right != cur) {
                prev = prev->right;
            }
            if (prev->right == nullptr) {
                // 建立临时链接，并继续向左遍历
                prev->right = cur;
                cur = cur->left;
            } else {
                // 断开链接，访问当前节点，转向右子树
                prev->right = nullptr;
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return result;
}

关键点：

• 通过修改指针临时改变树结构，遍历完成后恢复；
• 每个节点被访问两次（第一次建立链接，第二次断开链接），但时间复杂度仍为 O(n)。

总结

• 递归法直观但存在栈溢出风险；
• 迭代法显式管理栈，适合理解遍历过程；
• Morris 法节省空间，但会修改树结构（临时）。