c++中如何遍历二叉树_c++二叉树前中后序遍历_技术教程

递归遍历前中后序区别仅在于visit(root)位置：前序根左右、中序左根右、后序左右根；非递归中序用栈模拟，统一迭代法以nullptr标记访问时机。

递归实现前中后序遍历，核心就三个位置

前序、中序、后序的区别不在逻辑结构，而在 visit(root) 这句代码放在递归调用的哪个位置。只要记住：前序是“根左右”，中序是“左根右”，后序是“左右根”，对应到代码就是访问节点的时机不同。

假设二叉树节点定义为：

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

三种遍历的递归写法仅差一行顺序：

// 前序：根 → 左 → 右
void preorder(TreeNode* root, vector& res) {
    if (!root) return;
    res.push_back(root->val);  // ✅ 访问放最前
    preorder(root->left, res);
    preorder(root->right, res);
}
// 中序：左 → 根 → 右
void inorder(TreeNode* root, vector& res) {
if (!root) return;
inorder(root->left, res);   // ✅ 先递归左
res.push_back(root->val);    // ✅ 访问在中间
inorder(root->right, res);
}
// 后序：左 → 右 → 根
void postorder(TreeNode* root, vector& res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);    // ✅ 访问放最后
}

非递归中序遍历最常用，栈模拟调用过程

面试和工程中更常考非递归写法，尤其是中序——它天然对应 BST 的升序输出。关键不是背模板，而是理解栈里存的是“待回溯的根节点”，每次弹出即表示“左子树已处理完，现在该访问自己了”。

循环条件是 cur != nullptr || !stk.empty()，不能只判栈空
入栈动作必须在向左走之前做，否则会漏掉当前节点
每次从栈弹出后，立刻把 cur 设为 cur->right，进入右子树处理

vector inorderIterative(TreeNode* root) {
    vector res;
    stack stk;
    TreeNode* cur = root;
    while (cur || !stk.empty()) {
        while (cur) {
            stk.push(cur);
            cur = cur->left;  // 一路压左
        }
        cur = stk.top(); stk.pop();
        res.push_back(cur->val);  // 访问
        cur = cur->right;         // 切换到右子树
    }
    return res;
}

统一迭代法：用 null 标记访问时机

想一套代码通吃三种遍历？可以，但代价是空间多存一倍指针。思路是把“该访问根节点”这个动作也压栈，用 nullptr 作为标记。遇到 nullptr 就说明下一个节点就是该被访问的根。

以前序为例（中/后序只需调整入栈顺序）：

入栈顺序：先 root->right，再 nullptr，再 root->left（保证左先出）
遇到 nullptr 时，下一个弹出的就是要访问的节点
注意：必须检查 !stk.empty() 再取顶，否则运行时崩溃

vector preorderUniform(TreeNode* root) {
    vector res;
    stack stk;
    if (root) stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        if (node != nullptr) {
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left);
            stk.push(node);           // 根放最后
            stk.push(nullptr);       // 标记：下次该访问它
        } else {
            node = stk.top(); stk.pop();
            res.push_back(node->val);
        }
    }
    return res;
}