编码题：二叉树的中序遍历

Question

请用非递归的方式，实现二叉树的中序遍历。
编程语言不限（Java，C++，Python等）

Answer 1

下午好🌅🌅🌅
本答案参考通义千问

要实现二叉树的中序遍历（Inorder Traversal），并且要求使用非递归的方式，我们可以使用**栈（Stack）**来模拟递归过程。

---

✅ 什么是中序遍历？

中序遍历的顺序是：

1. 访问左子树
2. 访问当前节点
3. 访问右子树

对于一棵二叉树来说，中序遍历的结果是一个升序序列（如果该二叉树是一棵二叉搜索树）。

---

🧠 非递归中序遍历思路

1. 创建一个空栈。
2. 初始化当前节点为根节点。
3. 循环：
   • 如果当前节点不为空，则将其压入栈，并移动到其左子节点。
   • 如果当前节点为空，则从栈中弹出一个节点，记录它的值，然后将当前节点设为该节点的右子节点。
4. 重复上述步骤直到栈为空且当前节点也为 null。

---

📌 代码实现（Python）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    result = []
    stack = []
    current = root

    while current or stack:
        # 将所有左子节点压入栈
        while current:
            stack.append(current)
            current = current.left

        # 弹出栈顶元素并处理
        current = stack.pop()
        result.append(current.val)

        # 移动到右子节点
        current = current.right

    return result

---

🔍 示例说明

假设我们有如下二叉树：

    1
     \
      2
     /
    3

中序遍历结果应为：[1, 3, 2]

---

🧾 总结

非递归方式实现中序遍历的关键在于使用栈来保存遍历路径。

✅ 解决方案步骤如下：

1. 初始化栈和当前节点（从根节点开始）。
2. 不断向左走，将所有左子节点压入栈。
3. 当无法继续左走时，弹出栈顶元素，记录其值。
4. 转向右子节点，继续循环。
5. 直到栈为空且当前节点也为 null，遍历结束。

---

🧩 可选：C++ 实现（供参考）

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stack;
    TreeNode* current = root;

    while (current || !stack.empty()) {
        // 向左走到底
        while (current) {
            stack.push(current);
            current = current->left;
        }

        // 弹出并处理
        current = stack.top();
        stack.pop();
        result.push_back(current->val);

        // 转向右子节点
        current = current->right;
    }

    return result;
}

---

如有其他问题（如前序、后序遍历等），欢迎继续提问！