手撕代码是校园招聘技术面试中的常见环节，通常要求候选人现场在白板或纸上编写一段程序，考察其编程能力、逻辑思维、对数据结构与算法的掌握程度以及代码规范性。下面我将以一个典型的“手撕代码”面试题为例进行详细解析。 --- **示例问题：实现二叉树的中序遍历（Inorder Traversal），要求分别用递归和非递归方式实现。** --- - **正确答案**： 1. 递归版本：中序遍历顺序为：左子树 → 根节点 → 右子树 2. 非递归版本：使用栈模拟系统调用栈，显式控制访问顺序。 - **解答思路**：首先明确中序遍历的定义：对于每个节点，先处理其左子树，再访问该节点本身，最后处理右子树。 - 递归方法自然符合这一逻辑，直接调用函数自身即可。 - 非递归方法需要手动维护一个栈来保存尚未处理的节点。由于不能立即访问根节点，必须先将所有左子节点入栈，直到最左边的叶子节点，然后出栈并访问，再转向右子树。关键点在于理解“什么时候访问节点”——只有当某个节点的左子树已经被完全处理后，才能访问该节点。 - **深度知识讲解**： 1. **二叉树结构基础**：二叉树由节点组成，每个节点包含三个部分：值（val）、左孩子指针（left）、右孩子指针（right）。典型结构如下： ``` struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 2. **递归的本质**：递归利用了系统调用栈（call stack）自动保存函数上下文。每次函数调用都会压栈，返回时弹出。因此递归写法简洁但隐含空间开销。 3. **非递归与显式栈**：手动使用栈（如C++中的stack）可以模拟递归过程。这是理解编译器如何执行递归的重要途径，也是避免栈溢出（stack overflow）的一种手段。 4. **时间与空间复杂度分析**： - 时间复杂度：O(n)，n为节点数，每个节点被访问一次。 - 空间复杂度： - 递归：O(h)，h为树高，最坏情况下为O(n)（单链） - 非递归：同样O(h)，栈中最多存储从根到当前最深左路径的所有节点 5. **扩展考点**： - Morris遍历（线索化二叉树）可实现O(1)空间复杂度的中序遍历 - 前序、后序遍历的非递归写法差异（尤其是后序较复杂） - 如何重建二叉树？如何判断是否为BST？ - **代码示例（C++风格伪代码）**：定义节点类型： ``` struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 递归实现： ``` void inorderTraversalRecursive(TreeNode* root, vector& result) { if (root == nullptr) return; inorderTraversalRecursive(root->left, result); // 左 result.push_back(root->val); // 根 inorderTraversalRecursive(root->right, result); // 右 } // 调用接口 vector inorderTraversal(TreeNode* root) { vector res; inorderTraversalRecursive(root, res); return res; } ``` 非递归实现： ``` vector inorderTraversal(TreeNode* root) { vector result; stack stk; TreeNode* curr = root; while (curr != nullptr || !stk.empty()) { // 一直向左走到底，并将路径上所有节点入栈 while (curr != nullptr) { stk.push(curr); curr = curr->left; } // 此时 curr 为空，说明到达最左端 curr = stk.top(); stk.pop(); result.push_back(curr->val); // 访问当前节点 curr = curr->right; // 转向右子树 } return result; } ``` - **常见错误提醒**： - 忘记判断空指针导致段错误 - 在非递归中忘记更新 `curr = curr->right` - 错误地在入栈时就加入结果列表（这会变成前序） - 混淆栈的操作顺序（应先出栈再访问） - **进阶扩展建议**： 1. **Morris中序遍历（无栈，O(1)空间）**：利用空的右指针建立线索（thread），临时连接中序前驱。遍历完成后恢复原结构。思路简述： - 当前节点cur： - 若无左孩子：输出并进入右子树 - 若有左孩子：找到左子树的最右节点pre（即中序前驱） - 若pre的右指针为空：令pre->right = cur，进入左子树 - 若pre->right == cur：说明已遍历完左子树，断开链接，输出cur，进入右子树实现略复杂但极具面试价值。 2. **统一迭代框架（通用遍历模板）**：使用“颜色标记法”区分节点是第一次入栈还是第二次（准备访问）： ``` enum Color { WHITE, GRAY }; struct NodeColor { TreeNode* node; Color color; }; vector inorderTraversal(TreeNode* root) { vector res; stack stk; stk.push({root, WHITE}); while (!stk.empty()) { NodeColor nc = stk.top(); stk.pop(); if (nc.node == nullptr) continue; if (nc.color == WHITE) { // 按逆序入栈：右 -> 根 -> 左 stk.push({nc.node->right, WHITE}); stk.push({nc.node, GRAY}); stk.push({nc.node->left, WHITE}); } else { res.push_back(nc.node->val); } } return res; } ``` 此方法可用于统一实现前序、中序、后序遍历。 --- 总结： “手撕中序遍历”看似简单，实则涵盖递归机制、栈的应用、树的结构理解、边界处理等多重知识点。建议熟练掌握递归与非递归写法，并能清晰解释每一步的意义。同时了解Morris遍历和颜色标记法，有助于应对更高难度的变形题。

小米南京oc

全站热榜

创作者周榜