考研数据结构完整代码常见问题及解答技巧
常见问题解答
问题一：如何高效实现二叉树的遍历算法？
在考研数据结构中，二叉树的遍历是高频考点，常见的遍历方式有前序、中序、后序和层序遍历。许多同学在实现这些算法时容易混淆递归和非递归的写法，尤其是后序遍历的非递归实现。这里提供一个通用的解题思路：对于递归遍历，关键在于理解根节点、左子树和右子树的访问顺序；对于非递归遍历，通常借助栈来实现，但要注意栈中元素的压入和弹出顺序。以下是一个前序遍历的非递归实现示例：
cpp
void preorderTraversal(TreeNode root) {
if (root == nullptr) return;
stack<TreeNode> s;
s.push(root);
while (!s.empty()) {
TreeNode node = s.top();
s.pop();
visit(node); // 访问根节点
if (node->right != nullptr) s.push(node->right); // 先压右子树
if (node->left != nullptr) s.push(node->left); // 后压左子树