一、二叉树遍历：从递归到迭代，从理论到实战

二叉树遍历，说白了就是「怎么走遍这棵树的所有节点」。我刚开始学的时候，觉得这玩意儿不就是递归嘛，有啥好讲的？直到我在项目中遇到一个深层递归导致栈溢出的 bug，才意识到——嗯，迭代写法才是生产环境里的真功夫。

今天咱们就把前序、中序、后序、层序遍历一次性讲透。你想想看，掌握了这四种遍历，二叉树的最大深度、对称二叉树、路径总和这些经典题，基本就是手到擒来。

1.1 遍历的四种基本方式

先看一张图，把四种遍历的访问顺序理清楚：

1.2 递归实现——最直观的写法

递归写法，我个人觉得是理解遍历的最佳入口。代码短，逻辑清晰，看一眼就明白。

// 前序遍历：根 → 左 → 右
void preorder(TreeNode* root) {
    if (!root) return;
    visit(root);          // 先访问根
    preorder(root->left); // 再遍历左子树
    preorder(root->right);// 最后遍历右子树
}

// 中序遍历：左 → 根 → 右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

// 后序遍历：左 → 右 → 根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

1.3 迭代实现——生产环境的选择

递归虽好，但有个致命问题：当树深度很大时（比如1000层），递归会导致栈溢出。我在项目中就踩过这个坑——一个XML解析树深度超过2000，递归直接崩了。从那以后，我习惯用迭代写法处理大规模数据。

迭代的核心思想是「手动模拟栈」。前序和中序的迭代写法很相似，后序稍微绕一点。

前序遍历（迭代）

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root) st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);
        // 注意：先右后左，因为栈是后进先出
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

中序遍历（迭代）

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    
    while (cur || !st.empty()) {
        while (cur) {          // 一路向左，把沿途节点入栈
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        result.push_back(cur->val);
        cur = cur->right;      // 转向右子树
    }
    return result;
}

后序遍历（迭代）

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* lastVisited = nullptr;
    TreeNode* cur = root;
    
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        // 如果右子树为空或已访问，则访问当前节点
        if (!cur->right || cur->right == lastVisited) {
            result.push_back(cur->val);
            st.pop();
            lastVisited = cur;
            cur = nullptr;
        } else {
            cur = cur->right;
        }
    }
    return result;
}

1.4 层序遍历——BFS的典型应用

层序遍历用的是队列，不是栈。这个区别很重要——广度优先搜索（BFS）天然适合用队列实现。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数
        vector<int> level;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

1.5 经典例题：二叉树的最大深度

这道题，说白了就是「树有多少层」。递归解法极其优雅，一行核心逻辑搞定。

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

你想想看，这个递归是怎么工作的？

• 空节点深度为0
• 非空节点的深度 = 1 + 左右子树深度的最大值
• 递归到叶子节点时，左右子树深度都是0，返回1

迭代写法（层序遍历）也很直观：

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    
    while (!q.empty()) {
        depth++;
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return depth;
}

1.6 四种遍历的对比总结

遍历方式	访问顺序	递归实现	迭代实现	典型应用
前序	根→左→右	最简单	栈，先右后左入栈	序列化、复制树
中序	左→根→右	最简单	栈，一路向左	BST排序输出
后序	左→右→根	最简单	栈+lastVisited标记	删除树、表达式求值
层序	逐层从左到右	不适用	队列，记录每层大小	最短路径、右视图

嗯，到这里二叉树遍历的核心内容就讲完了。我个人觉得，理解遍历的关键不在于背代码，而在于想清楚「什么时候访问节点」——是在递归调用之前（前序）、之间（中序）、还是之后（后序）。想通了这一点，所有遍历题都是同一个套路。