企业官网建设流程全解析

产品网站怎么做超链接,潍坊市网站制作,苏州html网站模板,wordpress的登录密码Java版LeetCode热题100之二叉树的中序遍历#xff1a;从递归到Morris遍历的深度解析 本文将全面、深入地剖析 LeetCode 第94题「二叉树的中序遍历」#xff0c;不仅提供三种主流解法#xff08;递归、迭代、Morris#xff09;#xff0c;还涵盖算法原理、复杂度分析、面试…Java版LeetCode热题100之二叉树的中序遍历从递归到Morris遍历的深度解析本文将全面、深入地剖析 LeetCode 第94题「二叉树的中序遍历」不仅提供三种主流解法递归、迭代、Morris还涵盖算法原理、复杂度分析、面试技巧、实际应用场景以及相关题目拓展。全文约9500字适合准备面试、夯实基础或进阶学习的开发者阅读。一、原题回顾题目编号LeetCode 94题目名称Binary Tree Inorder Traversal二叉树的中序遍历难度等级Easy但蕴含深刻思想题目描述给定一个二叉树的根节点root返回它的中序遍历结果。示例示例 1输入root [1,null,2,3] 输出[1,3,2]示例 2输入root [] 输出[]示例 3输入root [1] 输出[1]约束条件树中节点数目在范围[0, 100]内-100 Node.val 100进阶要求递归算法很简单你可以通过迭代算法完成吗二、原题分析什么是中序遍历在二叉树的遍历中中序遍历Inorder Traversal是指按照以下顺序访问节点左子树 → 根节点 → 右子树这一顺序具有非常重要的性质对于一棵二叉搜索树BST其中序遍历的结果是一个严格递增的有序序列。这也是中序遍历在实际开发中最常见的应用场景之一。为什么这道题重要虽然题目标记为“简单”但它涵盖了递归与栈的等价性手动模拟系统调用栈空间复杂度优化Morris遍历指针操作与线索化思想可以说掌握这道题的三种解法就掌握了树遍历的核心思想。三、答案构思面对“中序遍历”问题我们可以从三个层次思考最直观的方式利用递归天然符合“分治”思想直接按“左-根-右”顺序递归。避免递归栈溢出使用显式栈Stack模拟递归过程实现迭代版本。极致空间优化采用 Morris 遍历在不使用额外栈空间的前提下完成遍历空间复杂度降至 O(1)。我们将依次实现这三种方法并深入分析其原理与适用场景。四、完整答案Java实现方法一递归RecursiveclassSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();inorder(root,res);returnres;}privatevoidinorder(TreeNodenode,ListIntegerres){if(nodenull)return;inorder(node.left,res);// 访问左子树res.add(node.val);// 访问根节点inorder(node.right,res);// 访问右子树}}✅优点代码简洁逻辑清晰易于理解。❌缺点依赖系统调用栈极端情况下如退化为链表可能导致栈溢出。方法二迭代Iterative with StackclassSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();DequeTreeNodestacknewLinkedList();TreeNodecurrroot;while(curr!null||!stack.isEmpty()){// 一路向左将路径上所有节点入栈while(curr!null){stack.push(curr);currcurr.left;}// 弹出栈顶即当前子树的最左节点currstack.pop();res.add(curr.val);// 转向右子树currcurr.right;}returnres;}}✅优点避免递归可控性强适用于深度较大的树。❌缺点仍需 O(n) 额外空间存储栈。方法三Morris 中序遍历Threaded Binary TreeclassSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegerresnewArrayList();TreeNodecurrroot;while(curr!null){if(curr.leftnull){// 无左子树直接访问当前节点并转向右子树res.add(curr.val);currcurr.right;}else{// 找到左子树的最右节点前驱节点TreeNodepredecessorcurr.left;while(predecessor.right!nullpredecessor.right!curr){predecessorpredecessor.right;}if(predecessor.rightnull){// 建立线索让前驱指向当前节点predecessor.rightcurr;currcurr.left;// 继续遍历左子树}else{// 已建立线索说明左子树已遍历完predecessor.rightnull;// 恢复树结构res.add(curr.val);currcurr.right;}}}returnres;}}✅优点空间复杂度 O(1)无需栈或递归。❌缺点代码复杂临时修改树结构虽会恢复面试中较少要求手写。五、代码分析递归解法分析核心思想函数调用栈自动保存“回溯点”。每次递归调用inorder(node.left)后系统栈会记住当前node的位置待左子树遍历完后继续执行res.add(node.val)和inorder(node.right)。终止条件node null即到达叶子节点的子节点。迭代解法分析关键技巧“先压栈再移动”。外层while控制整体流程只要当前节点非空或栈非空就继续。内层while负责将当前路径上所有左孩子压入栈直到最左叶子。弹出后访问该节点然后转向其右子树——右子树将成为新的“根”重复上述过程。记忆口诀“左到底弹出记右转走”Morris 遍历分析Morris 遍历的核心是利用空闲的右指针建立临时线索thread从而在不使用栈的情况下实现回溯。关键步骤若当前节点curr无左子树 → 直接访问转向右。若有左子树找到其左子树的最右节点即中序前驱。如果该前驱的right null→ 建立线索predecessor.right curr然后进入左子树。如果predecessor.right curr→ 说明左子树已遍历完断开线索访问curr转向右。为什么能保证每个节点被访问两次第一次建立线索时不访问值第二次通过线索返回时访问值并断开线索六、时间复杂度与空间复杂度分析方法时间复杂度空间复杂度是否修改原树递归O(n)O(h) ≈ O(n)否迭代O(n)O(h) ≈ O(n)否MorrisO(n)O(1)临时修改但会恢复其中h为树的高度。最坏情况退化为链表时h n最好情况完全平衡时h log n。详细解释时间复杂度均为 O(n)每个节点被访问常数次递归/迭代1次Morris最多2次总操作线性。空间复杂度递归和迭代依赖栈深度为树高h。Morris 利用树本身的空指针仅用几个变量故 O(1)。⚠️ 注意虽然 Morris 空间最优但在多线程环境或不允许修改输入的场景下不可用。七、常见问题解答FAQQ1为什么中序遍历对 BST 如此重要答因为 BST 的定义是“左 根 右”所以中序遍历结果必然是升序序列。可用于验证一棵树是否为 BST获取 BST 的有序元素列表实现 BST 的范围查询如第 k 小元素Q2迭代写法中为什么内层 while 要一直往左走答因为中序遍历必须先访问最左边的节点。通过不断将左孩子入栈我们确保了栈顶始终是当前未访问子树中最左的节点符合中序顺序。Q3Morris 遍历会不会破坏原树结构答不会。虽然过程中会临时修改某些节点的right指针但在第二次访问该节点时会立即恢复predecessor.right null。遍历结束后树结构与原始完全一致。Q4面试时应该优先写哪种解法答如果没特别要求先写递归展示基础能力。如果面试官说“不用递归”则写迭代考察栈的理解。Morris 通常作为加分项除非明确要求 O(1) 空间否则不必主动写。八、优化思路1. 递归 → 尾递归优化Java 不支持尾递归优化因此无法降低栈空间。但在 Scala、Erlang 等语言中可考虑。2. 迭代 → 使用 ArrayDeque 替代 LinkedListArrayDeque作为栈性能优于LinkedList缓存友好无节点对象开销。可替换为DequeTreeNodestacknewArrayDeque();3. Morris 遍历 → 提前判断是否需要线索若已知树是平衡的递归/迭代的栈深度仅为 O(log n)此时 Morris 的常数开销可能得不偿失。4. 并行遍历中序遍历具有强顺序依赖必须先左后根再右难以并行化。但若只需收集所有节点值不要求顺序可用 BFS 并行处理。九、数据结构与算法基础知识点回顾1. 二叉树的三种 DFS 遍历遍历方式顺序应用场景前序Preorder根 → 左 → 右复制树、序列化中序Inorder左 → 根 → 右BST 有序输出后序Postorder左 → 右 → 根删除树、计算目录大小2. 递归与栈的关系递归本质是系统维护的隐式栈。任何递归算法都可转化为迭代 显式栈。栈中存储的是“待完成的任务”如访问根、遍历右子树。3. 线索二叉树Threaded Binary Tree利用空指针域存储前驱/后继信息。Morris 遍历是临时线索化的经典应用。可实现 O(1) 空间的中序遍历且支持双向遍历。4. 空间复杂度 vs 辅助空间总空间复杂度 输入空间 辅助空间本题中输入树占 O(n)但我们讨论的“空间复杂度”通常指额外辅助空间。Morris 的 O(1) 指的是辅助空间为常数不包括输入本身。十、面试官提问环节模拟对话面试官你写了递归解法能说说它的空间复杂度吗你最坏情况下比如树退化成链表递归深度为 n所以空间复杂度是 O(n)。面试官如果树很大递归可能导致栈溢出怎么办你可以改用迭代栈的方式手动控制栈的使用避免系统栈溢出。面试官有没有办法做到 O(1) 空间你有的Morris 遍历。它通过临时修改树的指针建立线索遍历完再恢复空间复杂度 O(1)。面试官Morris 遍历的时间复杂度是多少为什么你O(n)。虽然每个节点最多被访问两次一次建线索一次断线索但常数倍不影响大 O 表示法。面试官如果这棵树是 BST中序遍历有什么特殊性质你结果是严格递增的有序序列。这也是验证 BST 的常用方法。面试官能否用中序遍历解决“二叉搜索树中第 k 小的元素”你可以。中序遍历到第 k 个元素即可返回甚至可以提前终止。十一、这道算法题在实际开发中的应用1. 数据库索引遍历B 树数据库索引结构的叶节点链表本质上是中序遍历的线性展开支持高效范围查询。2. 表达式树求值表达式(a b) * c可表示为二叉树中序遍历可还原中缀表达式需加括号处理优先级。3. 文件系统目录遍历虽然通常用 BFS层级展示但某些工具如tree命令的缩进输出逻辑类似 DFS 中序。4. 编译器语法树处理在 AST抽象语法树中中序遍历可用于生成人类可读的代码字符串。5. 内存管理中的对象图遍历垃圾回收器遍历对象引用图时若需按特定顺序处理如 finalizer可能借鉴树遍历思想。十二、相关题目推荐掌握本题后可挑战以下进阶题目题号题目关联点144二叉树的前序遍历同系列顺序不同145二叉树的后序遍历更复杂的迭代写法98验证二叉搜索树中序遍历 有序性判断230二叉搜索树中第K小的元素中序遍历提前终止538把二叉搜索树转换为累加树反向中序遍历右→根→左105从前序与中序遍历序列构造二叉树重建树的经典问题106从中序与后序遍历序列构造二叉树同上173二叉搜索树迭代器封装中序遍历为迭代器重点推荐第 98、230、538 题都是中序遍历在 BST 中的典型应用。十三、总结与延伸核心收获三种解法代表三种思维层次递归简洁优雅体现分治思想迭代手动控栈理解系统底层Morris极致优化展现算法创造力中序遍历 ≠ 仅仅输出节点值它是一种访问策略背后是“左-根-右”的处理顺序。空间换时间 or 时间换空间Morris 用“多访问一次”换取“零额外空间”是经典权衡。延伸思考能否统一前序、中序、后序的迭代写法可以通过在栈中记录“状态”如 0未处理1已处理左2已处理右但代码复杂。Morris 能用于前序/后序吗前序可以访问时机不同后序较复杂需逆序输出一般不推荐。如果树是 N 叉树还有中序遍历吗没有标准定义。N 叉树通常只有前序和后序。最后建议面试准备务必熟练写出递归和迭代版本。工程实践优先选择递归可读性高除非有栈溢出风险。算法竞赛掌握 Morris应对 O(1) 空间限制。结语一道“简单”题藏着算法世界的万千气象。从递归的优雅到栈的掌控再到 Morris 的巧思每一步都是对计算机科学本质的探索。愿你在刷题路上不止于 AC更在于理解与创造。欢迎点赞、收藏、评论交流你的支持是我持续输出高质量内容的动力