先序遍历递归实现最直观，因其天然契合“根→左→右”定义：先处理当前节点，再递归遍历左、右子树；关键需首行判空（if root==null return），访问操作必须置于左右递归调用之前。
先序遍历的递归实现为什么最直观
因为先序遍历的定义就是“根→左→右”，递归天然契合这个结构。只要在访问节点时先处理当前节点，再递归左子树、右子树，逻辑就完全对齐。
常见错误是把访问顺序写反，比如先递归再打印，结果变成后序；或者漏掉空指针判断，导致 segmentation fault。
- 必须在进入函数第一行加
if (root == nullptr) return; - 访问操作（如打印值）必须放在递归调用
left和right之前 - 如果需要收集结果而非打印，用引用传入
std::vector<int>& result</int>更高效，避免频繁拷贝
void preorder(TreeNode* root, std::vector<int>& result) {
if (root == nullptr) return;
result.push_back(root->val); // 先访问
preorder(root->left, result); // 再左
preorder(root->right, result); // 最后右
}</int>
非递归版本用栈模拟时要注意什么
手动栈实现本质是复现系统调用栈的行为：每次弹出一个节点，立即压入其右、左子节点（注意顺序！），这样左子节点会先被弹出，符合先序要求。
容易踩的坑是压栈顺序写成“左→右”，结果遍历变成根→右→左；或者忘记判空就直接压栈，导致栈里塞入大量 nullptr，后续解引用崩溃。
- 压栈前必须检查子节点是否为
nullptr - 右子节点要先压、左子节点后压，才能保证左子节点先出栈
- 使用
std::stack<treenode></treenode>，不要用std::stack<treenode></treenode>（会触发拷贝构造，且丢失指针关系）
std::vector<int> preorderIterative(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<treenode> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top(); stk.pop();
result.push_back(node->val);
if (node->right) stk.push(node->right); // 先压右
if (node->left) stk.push(node->left); // 后压左
}
return result;
}</treenode></int></int>
迭代器风格封装时如何避免悬空指针
如果把先序遍历封装成类似 STL 迭代器的类（如 PreorderIterator），核心难点在于：树结构可能在迭代过程中被外部修改，而迭代器内部缓存的栈或指针就会失效。
这不是语法问题，而是设计约束——C++ 标准库容器迭代器也要求“不保证多线程安全”和“不保证底层结构不变”。所以必须明确文档化该限制，且在调试版中可加入断言验证节点有效性。
- 内部栈应保存
TreeNode*，而非TreeNode&（引用不能作为容器元素） - 构造时做一次完整路径预计算（如把从根到最左叶的路径全压栈）能减少运行时判断，但增加空间开销
- 不建议在迭代器里动态 new/delete 节点；若需长期持有，应配合智能指针（如
std::shared_ptr<treenode></treenode>）管理生命周期
LeetCode 验证时输出格式不匹配怎么办
很多题（如 LeetCode 144）要求返回 std::vector<int></int>，但本地测试时可能习惯用 std::cout 打印。提交前务必确认函数签名和返回值类型，否则编译失败或输出为空。
另一个高频问题是输入为空树（root == nullptr）时，忘了返回空 vector，导致未定义行为或越界访问。
- LeetCode 测试用例包含极端情况：空树、单节点、满二叉树、链状树，都要覆盖
- 用
assert(result.size() == expected.size())和逐元素比对，比肉眼观察输出更可靠 - 如果题目要求“原地修改”或“O(1) 空间”，那递归版本因隐式栈不满足条件，必须用 Morris 遍历——但那是另一套逻辑，别硬套标准递归
实际写的时候，递归够用就别强行迭代；真要迭代，栈顺序和空指针检查这两处错一个，程序当场静默崩溃或逻辑错乱。Morris 遍历虽省空间，但破坏树结构，除非题目明确要求，否则不值得引入复杂度。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
