算法

二叉树的中序遍历

loser

25 Aug 2026 • 7 min read

给定一个二叉树的根节点 root，返回它的中序遍历结果。

中序遍历的访问顺序是：

左子树 -> 根节点 -> 右子树

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶： 递归算法很简单，你可以通过迭代算法完成吗？

解法一（递归）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }

private:
    void dfs(TreeNode* node, vector<int>& ans) {
        if (node == nullptr)
        {
            return;
        }

        dfs(node->left, ans);
        ans.push_back(node->val);
        dfs(node->right, ans);
    }
};

解法二（迭代栈）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while (cur != nullptr || !st.empty())
        {
            while (cur != nullptr)
            {
                st.push(cur);
                cur = cur->left;
            }

            cur = st.top();
            st.pop();
            ans.push_back(cur->val);

            cur = cur->right;
        }

        return ans;
    }
};

核心思想

中序遍历的顺序固定为：

左子树 -> 根节点 -> 右子树

递归写法最直观，因为二叉树本身就是递归结构。

对于任意一个节点，只要按照这个顺序处理：

先遍历左子树
再访问当前节点
最后遍历右子树

就能得到整棵树的中序遍历。

这题最关键的观察是：

中序遍历中，一个节点必须等到它的整棵左子树都访问完成后，才可以访问自己。

迭代写法就是用栈模拟递归过程。

不断沿着左孩子往下走，把沿途节点压入栈中。

当走到空节点时，说明当前这条路径最左边的节点可以被访问。

访问完这个节点后，再转向它的右子树，继续重复同样的过程。

解法一：递归

递归函数 dfs(node, ans) 表示：

把以 node 为根的子树，按照中序遍历顺序加入 ans

如果 node == nullptr，说明当前子树为空，直接返回。

否则按照中序遍历顺序执行：

dfs(node->left, ans);
ans.push_back(node->val);
dfs(node->right, ans);

这三行代码正好对应：

左 -> 根 -> 右

解法二：迭代栈

递归本质上依赖系统调用栈。

如果不用递归，就需要手动维护一个栈。

栈中保存的是：

已经经过，但还不能立刻访问的节点

为什么不能立刻访问？

因为中序遍历要求先访问左子树。

所以当来到一个节点 cur 时，不能马上把它加入答案，而是要先把它压入栈，然后继续走向左孩子：

st.push(cur);
cur = cur->left;

当 cur == nullptr 时，说明左边已经走到底。

这时栈顶节点的左子树已经处理完，可以访问栈顶节点：

cur = st.top();
st.pop();
ans.push_back(cur->val);

访问完当前节点后，中序遍历下一步应该处理它的右子树：

cur = cur->right;

整个过程不断重复，直到当前指针为空并且栈也为空。

为什么迭代写法等价于递归

递归遍历左子树时，系统会暂时保存当前节点，等左子树处理完以后再回到当前节点。

迭代写法中的栈也在做同样的事情。

当沿着左孩子不断下降时，所有暂时不能访问的祖先节点都会被压入栈。

走到最左侧以后，栈顶节点就是当前最应该访问的节点。

访问它之后，再进入右子树。

所以迭代栈模拟的正是递归中：

先进入左子树 -> 回到根节点 -> 再进入右子树

这一过程。

边界情况

如果二叉树为空：

root = []

递归解法中，dfs(nullptr, ans) 会直接返回，答案是空数组。

迭代解法中，cur == nullptr 且栈为空，循环不会执行，答案也是空数组。

如果二叉树只有一个节点：

root = [1]

它没有左右子树，中序遍历结果就是 [1]。

如果树退化成一条链，递归和迭代仍然按照相同规则处理。

正确性证明

我们证明：两个解法都能返回二叉树的中序遍历结果。

结论 1：递归解法对任意子树都按照中序顺序访问

对于空子树，递归函数直接返回，不加入任何节点，结果正确。

对于非空子树，递归函数先遍历左子树，再访问根节点，最后遍历右子树。

这正是中序遍历的定义。

如果左右子树都能被正确中序遍历，那么把左子树结果、根节点、右子树结果依次连接，就得到当前子树的中序遍历。

因此递归解法正确。

结论 2：迭代解法访问节点前，其左子树已经访问完成

迭代过程中，只要 cur 不为空，就持续把 cur 压入栈，并转向 cur->left。

因此一个节点被压入栈后，不会立刻访问，而是先继续处理它的左子树。

只有当左边走到空节点时，算法才弹出栈顶节点并访问它。

所以每个节点被访问时，它的左子树已经访问完成。

结论 3：迭代解法访问节点后，会继续访问它的右子树

当算法弹出并访问节点 cur 后，会执行：

cur = cur->right;

这表示接下来处理它的右子树。

右子树内部仍然按同样规则先一路向左，再访问节点，再进入右子树。

因此每个节点访问后，都会按照中序遍历要求继续处理右子树。

结论 4：迭代解法不会遗漏或重复访问节点

每个节点只会在沿左路径下降时被压入栈一次。

每个被压入栈的节点之后都会被弹出并访问一次。

访问后算法转向它的右子树，右子树中的节点也会按同样方式入栈和出栈。

所以每个节点都会被访问一次，且不会重复访问。

得出结论

由结论 1 可知，递归解法符合中序遍历定义。

由结论 2 和结论 3 可知，迭代解法对每个节点都满足“左 -> 根 -> 右”的访问顺序。

由结论 4 可知，迭代解法不会遗漏或重复节点。

因此两个解法都能正确返回二叉树的中序遍历结果。

举例理解

以：

root = [1,null,2,3]

为例，这棵树可以理解为：

中序遍历顺序是：

先遍历节点 1 的左子树，左子树为空
访问节点 1
遍历节点 1 的右子树，也就是以 2 为根的子树
对节点 2，先遍历左子树 3
访问节点 3
再访问节点 2

所以最终结果是：

[1,3,2]

用迭代栈看过程：

当前动作	栈	结果
压入 `1`，转向左子树	`[1]`	`[]`
左子树为空，弹出并访问 `1`	`[]`	`[1]`
转向 `1` 的右子树 `2`	`[]`	`[1]`
压入 `2`，转向左子树 `3`	`[2]`	`[1]`
压入 `3`，转向左子树	`[2,3]`	`[1]`
左子树为空，弹出并访问 `3`	`[2]`	`[1,3]`
`3` 的右子树为空，弹出并访问 `2`	`[]`	`[1,3,2]`

最终得到：

[1,3,2]

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点都会被访问一次。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点最多入栈一次、出栈一次。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自显式维护的栈。

如果题目要求不用递归，解法二就是推荐写法。