企业官网建设流程全解析

重庆免费做网站,阿里巴巴可以做公司网站吗,大学生做网站兼职,xmlrpc wordpress开启我的二叉树中序遍历解题思路#xff08;C递归实现#xff09;在刷LeetCode 94题「二叉树的中序遍历」时#xff0c;我采用了简洁直观的递归写法#xff0c;核心思路围绕中序遍历「左子树→根节点→右子树」的核心顺序展开。本文将详细讲解我的代码逻辑、执行流程及优化方向…我的二叉树中序遍历解题思路C递归实现在刷LeetCode 94题「二叉树的中序遍历」时我采用了简洁直观的递归写法核心思路围绕中序遍历「左子树→根节点→右子树」的核心顺序展开。本文将详细讲解我的代码逻辑、执行流程及优化方向适合作为个人学习笔记或博客分享。一、题目回顾题目要求给定二叉树的根节点 root 返回其中序遍历的节点值列表。- 树中节点数目范围 [0, 100]- 节点值范围 [-100, 100]示例输入 root [1,null,2,3] 输出 [1,3,2] 遍历顺序1的左子树→1→2的左子树3→3→2→2的右子树二、我的代码实现cpp/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {public:vectorint result; // 存储遍历结果的全局变量vectorint inorderTraversal(TreeNode* root) {if(root NULL){ // 终止条件当前节点为空直接返回结果return result;}inorderTraversal(root-left); // 1. 递归遍历左子树result.push_back(root-val); // 2. 访问当前根节点加入结果集inorderTraversal(root-right); // 3. 递归遍历右子树return result;}};三、代码逻辑详解1. 核心思路递归的本质是利用系统调用栈自动维护遍历顺序无需手动管理栈结构完全贴合中序遍历的逻辑- 先深入左子树的最底层直到节点为空- 回溯时访问当前根节点将值存入结果集- 最后递归遍历右子树重复上述过程。2. 关键部分解析1全局变量 result- 作用存储遍历后的节点值避免每次递归时重新创建向量减少拷贝开销。- 注意若多次调用 inorderTraversal 函数需在每次调用前清空 result 但本题为单次调用无需处理。2终止条件 if(root NULL)- 当递归到空节点时左子树或右子树遍历完毕直接返回当前结果集避免空指针访问错误。3递归流程1. inorderTraversal(root-left) 优先遍历左子树直到触发终止条件2. result.push_back(root-val) 左子树遍历完成后访问当前根节点将值加入结果集3. inorderTraversal(root-right) 遍历当前节点的右子树重复「左→根→右」流程。3. 执行流程演示以示例1为例输入 root [1,null,2,3] 二叉树结构如下plaintext1\2/3执行步骤1. 调用 inorderTraversal(1) → 先执行 inorderTraversal(1-left) 1的左子树为空返回空结果集2. 将1的值加入 result 此时 result [1] 3. 调用 inorderTraversal(1-right) 即节点24. 调用 inorderTraversal(2-left) 即节点35. 调用 inorderTraversal(3-left) 3的左子树为空返回6. 将3的值加入 result 此时 result [1,3] 7. 调用 inorderTraversal(3-right) 3的右子树为空返回8. 回到节点2将2的值加入 result 此时 result [1,3,2] 9. 调用 inorderTraversal(2-right) 2的右子树为空返回10. 遍历结束返回 result [1,3,2] 。四、代码优缺点分析优点1. 简洁直观代码仅需几行核心逻辑完全贴合中序遍历的定义易写易理解2. 无额外空间开销无需手动维护栈依赖系统栈代码简洁度高3. 适配题目约束本题节点数≤100递归深度不会触发栈溢出完全适用。缺点1. 递归深度限制若二叉树为斜树如链状深度10^4会触发栈溢出C默认递归栈深度约为1e42. 全局变量风险若函数被多次调用 result 中的旧数据会影响新结果需手动清空3. 可读性依赖递归理解对递归不熟悉的开发者可能难以追踪执行流程。五、优化方向可选拓展1. 避免全局变量使用局部变量辅助函数将 result 改为局部变量通过辅助函数传递引用避免全局变量的副作用cppclass Solution {public:vectorint inorderTraversal(TreeNode* root) {vectorint result; // 局部变量dfs(root, result); // 辅助函数传递引用return result;}private:// 辅助递归函数遍历以node为根的子树结果存入resvoid dfs(TreeNode* node, vectorint res) {if (node nullptr) return;dfs(node-left, res);res.push_back(node-val);dfs(node-right, res);}};优势每次调用 inorderTraversal 都会创建新的 result 避免多次调用时的数据污染更符合函数设计规范。2. 迭代实现解决栈溢出问题若需处理大规模二叉树可手动模拟栈实现迭代遍历避免递归栈溢出cpp#include stackclass Solution {public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* stk;TreeNode* cur root;while (cur ! nullptr || !stk.empty()) {// 所有左子节点入栈while (cur ! nullptr) {stk.push(cur);cur cur-left;}// 出栈访问根节点cur stk.top();stk.pop();result.push_back(cur-val);// 遍历右子树cur cur-right;}return result;}};优势空间复杂度仍为 O(h)h为树的高度但无递归深度限制适用于任意规模的二叉树。六、注意事项1. 空树处理当 root nullptr 时函数直接返回空的 result 无需额外判断2. 节点值范围题目中节点值可能为负数-100≤val≤100 push_back 可直接处理无需特殊逻辑3. 递归栈溢出本题节点数≤100递归版本完全安全若题目无节点数限制优先选择迭代版本或Morris遍历空间复杂度O(1)。七、总结我的解法以递归为核心充分利用系统栈简化代码完美贴合中序遍历的「左→根→右」逻辑适合入门理解和小规模场景。若需优化可通过「局部变量辅助函数」解决全局变量问题或用迭代法处理大规模二叉树。中序遍历是二叉树的基础遍历方式尤其在二叉搜索树中能获取升序序列掌握递归与迭代两种实现能轻松应对各类相关题目。如果有其他优化思路或疑问欢迎在评论区交流博客拓展建议1. 可添加递归调用栈的示意图直观展示每次递归的入栈、出栈过程2. 补充Morris遍历的实现空间复杂度O(1)提升博客深度3. 对比前序、中序、后序遍历的递归写法差异帮助读者举一反三。