二叉树的中序遍历 图解题解

中序遍历的顺序到底是什么

中序遍历要求对每个节点都遵守同一条规则：左子树全部访问完，才轮到根，最后才是右子树。「中」指的是根被夹在中间输出。这个定义是递归的——访问左子树时，内部同样按左根右展开。由此能直接推出一个结论：整棵树第一个被访问的节点，一定是从根一路沿左孩子走到底的那个最左下节点；最后一个则是最右下节点。

递归写法为什么天然正确

递归版几乎是定义的直译：先调用 inorder(root.left)，再收集 root.val，最后调用 inorder(root.right)。「左子树必须先处理完」这条约束不需要任何额外代码来保证——函数调用栈替你保证了：inorder(root.left) 不返回，后面两行根本不会执行。思路上递归是最清晰的版本，但面试常追问「不用递归怎么写」，所以显式栈的迭代版才是本题的重点。

迭代版为什么要一路向左压栈

不用递归，就得自己接管调用栈的职责，这正是显式栈的作用。从当前节点出发一路向左，把沿途节点依次压栈：栈里存的是「左子树还没处理完、暂时不能访问」的节点，同时也是之后往回走的路。走到最左尽头时，栈顶恰好是所有未访问节点中最靠左的那个——它没有左孩子或左子树已清空，按左根右的规则，此刻正该轮到它。

弹出即访问，凭什么成立

整个迭代过程维持一条不变量：任何节点被弹出时，它的左子树必然已经全部访问完。原因很直接——节点入栈之后，算法先钻进它的左子树，左边全部处理完毕才可能弹到它。所以弹出即可放心访问，访问完把指针转向右子树，对右子树再重复「一路向左压栈」。循环条件写成栈非空或当前指针非空，两者都空才说明整棵树走完。

复杂度与常见的翻车点

时间 O(n)：每个节点恰好入栈一次、出栈一次，n 为节点数。空间 O(H)：栈里最多同时存一条从根到当前位置的左链，H 为树高，链状树最坏 O(n)。两个高频错误：把顺序写成根左右，那是前序遍历，结果整体错位；迭代时压栈方向搞反，弹出的就不再是当前最左的未访问节点。若被追问 O(1) 空间的做法，可以提 Morris 中序遍历：借叶子的空右指针临时指回后继节点，遍历完再拆掉线索，时间仍 O(n)，空间降到 O(1)，属进阶考点。

Python

def inorderTraversal(root):
    res, stack = [], []
    cur = root
    while stack or cur:
        while cur:            # 一路向左压栈
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()    # 弹出即访问（左已处理完）
        res.append(cur.val)  # 访问根
        cur = cur.right      # 再转向右子树
    return res

C++

vector<int> inorderTraversal(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while(!st.empty() || cur){
        while(cur){ st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

Java

public List<Integer> inorderTraversal(TreeNode root){
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while(!stack.isEmpty() || cur != null){
        while(cur != null){ stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}