c++如何实现二叉树的先序遍历_c++递归与非递归写法【核心】

先序遍历递归最常用因其逻辑最贴近定义（根→左→右），代码直观；但需防栈溢出，须设终止条件、正确访问顺序，并用引用传vector避免拷贝。

先序遍历递归写法为什么最常用？

因为逻辑最贴近定义：根 → 左子树 → 右子树，代码几乎就是人话翻译。但要注意栈溢出风险——深度超过系统默认栈限制（通常几千层）就会崩，比如退化成链表的二叉搜索树。

实操建议：

• 递归函数必须有明确终止条件：if (root == nullptr) return;
• 访问顺序不能错：先处理root->val，再递归preorderTraversal(root->left)，最后preorderTraversal(root->right)
• 如果需要返回结果而非仅打印，用引用传入vector& res避免频繁拷贝

示例片段：

Interior AI

AI室内设计，上传室内照片自动帮你生成多种风格的室内设计图

下载

void preorder(TreeNode* root, vector& res) {
    if (!root) return;
    res.push_back(root->val);  // 根
    preorder(root->left, res);  // 左
    preorder(root->right, res); // 右
}

非递归先序遍历怎么用栈模拟？

核心是“边访问边压右再压左”——因为栈是后进先出，要让左子树先被弹出，就得先把右子树压进去。

立即学习“C++免费学习笔记（深入）”；

常见错误现象：

• 压栈顺序反了（先压左再压右），导致遍历变成根→右→左
• 忘记判空就直接访问root->left，触发段错误
• 循环条件写成!st.empty()却没在循环内弹栈，死循环

实操建议：

• 初始化栈时只压入root（前提是root != nullptr）
• 每次pop一个节点，立刻访问；若它有右孩子，压右；若有左孩子，压左
• 用stack st，别用stack存值——你得靠指针继续往下走

示例片段：

vector preorderTraversal(TreeNode* root) {
    vector res;
    if (!root) return res;
    stack st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);
        if (node->right) st.push(node->right); // 先压右
        if (node->left)  st.push(node->left);  // 后压左
    }
    return res;
}

迭代器风格或统一遍历框架下怎么写？

如果你正在封装一个支持begin()/end()的BinaryTree类，或者想和中序/后序共享结构，就得用“访问标记”方式：每个节点入栈两次，第一次带标记false表示待展开，第二次带true表示可访问。

性能影响明显：空间多一倍，且每次都要判断标记位；但好处是三种遍历只需改几行。

关键点：

• 用pair代替裸指针
• 遇到bool == false时，按先序顺序逆序压栈（右→左→根），并把根的标记设为true
• 遇到bool == true，直接res.push_back

LeetCode 提交时要注意哪些边界？

题干说“二叉树节点数 ≤ 10⁴”，但不代表不会给你nullptr输入。很多本地测试通过的代码在线上挂，就是因为没处理空树。

容易被忽略的地方：

• TreeNode定义里没有默认构造函数，别写TreeNode()初始化
• C++11 后推荐用nullptr而非NULL或0作为空指针
• 非递归版本中，stack不支持front()，只能用top()；别和queue搞混
• 递归版若用vector返回，别在每次递归里新建——要么传引用，要么用移动语义return std::move(res)

真正麻烦的不是写法本身，而是当树极深又极偏时，递归爆栈、迭代多耗内存、统一框架多绕两步——选哪种，得看你的场景到底卡在哪。