LeetCode 94 二叉树中序遍历全解递归、显式栈迭代与 Morris 遍历三方案leetcode1 多语言源码对照【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode中序遍历Inorder Traversal以左子树 → 当前节点 → 右子树的顺序访问二叉树节点是深度优先搜索DFS的三种经典遍历之一对二叉搜索树BST而言中序遍历恰好输出递增有序序列因此它也是kth-smallest-integer-in-bst、valid-binary-search-tree等一批 BST 题目的解题基石。本文以仓库 articles/binary-tree-inorder-traversal.md 为骨架系统讲解递归、显式栈迭代、Morris 遍历三种实现方案并对照 python/0094-binary-tree-inorder-traversal.py、cpp/0094-binary-tree-inorder-traversal.cpp、c/0094-binary-tree-inorder-traversal.c、rust/0094-binary-tree-inorder-traversal.rs 等仓库源码帮你把这道题吃透到可以举一反三的程度。读完你将掌握三种写法的算法步骤、多语言实现与复杂度差异并能用中序遍历直接解决 BST 相关变体题。前置知识动手实现之前建议先确认自己熟悉以下三块基础二叉树结构理解节点如何通过left、right指针连接父子关系。仓库各语言题解文件开头都给出了对应语言的TreeNode定义例如 typescript/0094-binary-tree-inorder-traversal.ts 中的class TreeNode { val; left; right }c/0094-binary-tree-inorder-traversal.c 中对应的struct TreeNode。递归用递归调用天然地表达先左、再中、后右的遍历顺序递归深度即树高。栈Stack用显式栈模拟递归调用栈从而把递归写法改写成迭代写法避免递归深度过大时的栈溢出风险。解法一递归深度优先搜索Recursive DFS直觉中序遍历的访问顺序是固定的先左子树再当前节点最后右子树。递归函数天然携带当前子树根节点这一上下文因此只需要在递归函数中按这个顺序依次执行即可。对于二叉搜索树这一顺序会使输出的节点值严格递增——这正是中序这个名字的由来。算法步骤创建一个结果列表res用于存储节点值。定义递归辅助函数inorder(node)若node为null立即返回递归基。先递归调用inorder(node.left)遍历左子树。将当前节点值node.val追加到res。再递归调用inorder(node.right)遍历右子树。整棵树遍历完成后返回res。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def inorder(node): if not node: return inorder(node.left) res.append(node.val) inorder(node.right) inorder(root) return respublic class Solution { private ListInteger res; public ListInteger inorderTraversal(TreeNode root) { res new ArrayList(); inorder(root); return res; } private void inorder(TreeNode node) { if (node null) { return; } inorder(node.left); res.add(node.val); inorder(node.right); } }class Solution { vectorint res; public: vectorint inorderTraversal(TreeNode* root) { inorder(root); return res; } private: void inorder(TreeNode* node) { if (!node) { return; } inorder(node-left); res.push_back(node-val); inorder(node-right); } };class Solution { inorderTraversal(root) { const res []; const inorder (node) { if (!node) return; inorder(node.left); res.push(node.val); inorder(node.right); }; inorder(root); return res; } }public class Solution { public Listint InorderTraversal(TreeNode root) { Listint res new Listint(); void Inorder(TreeNode node) { if (node null) return; Inorder(node.left); res.Add(node.val); Inorder(node.right); } Inorder(root); return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} var inorder func(node *TreeNode) inorder func(node *TreeNode) { if node nil { return } inorder(node.Left) res append(res, node.Val) inorder(node.Right) } inorder(root) return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() fun inorder(node: TreeNode?) { if (node null) return inorder(node.left) res.add(node.val) inorder(node.right) } inorder(root) return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() func inorder(_ node: TreeNode?) { guard let node node else { return } inorder(node.left) res.append(node.val) inorder(node.right) } inorder(root) return res } }impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); Self::inorder(root, mut res); res } fn inorder(node: OptionRcRefCellTreeNode, res: mut Veci32) { if let Some(n) node { let n n.borrow(); Self::inorder(n.left, res); res.push(n.val); Self::inorder(n.right, res); } } }仓库中 rust/0094-binary-tree-inorder-traversal.rs 就是这一递归思路的直接落地由于 Rust 采用RcRefCellTreeNode的共享所有权模型代码里通过v.borrow()获取节点可变内部值再递归访问v.left、v.right与上述伪代码完全对应。同理typescript/0094-binary-tree-inorder-traversal.ts 用默认参数list: Arraynumber []把结果数组一路向下传递本质上也是同一个递归模板。时间与空间复杂度时间复杂度$O(n)$其中 $n$ 为节点总数每个节点恰好被访问一次。空间复杂度递归调用栈深度取决于树高最坏情况退化为链表为 $O(n)$输出数组本身还需 $O(n)$ 空间。解法二迭代深度优先搜索Iterative DFS显式栈直觉递归依赖系统调用栈而我们可以用显式栈来模拟这一过程。核心技巧是尽可能向左深入把沿途经过的节点全部压栈当无法继续向左时从栈顶弹出一个节点处理然后转向它的右子树。栈的作用正是记住那些左子树处理完毕后还需要回头处理的节点。算法步骤初始化空的结果列表res和空栈stack。令当前节点cur root。当cur不为null或栈非空时循环只要cur不为null将cur压栈然后cur cur.left一路向左。从栈中弹出一个节点将其值加入res。令cur 弹出节点的右孩子。循环结束后返回res。多语言实现class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return respublic class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); StackTreeNode stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); res.add(cur.val); cur cur.right; } return res; } }class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stack; TreeNode* cur root; while (cur || !stack.empty()) { while (cur) { stack.push(cur); cur cur-left; } cur stack.top(); stack.pop(); res.push_back(cur-val); cur cur-right; } return res; } };class Solution { inorderTraversal(root) { const res []; const stack []; let cur root; while (cur || stack.length 0) { while (cur) { stack.push(cur); cur cur.left; } cur stack.pop(); res.push(cur.val); cur cur.right; } return res; } }public class Solution { public IListint InorderTraversal(TreeNode root) { Listint res new Listint(); StackTreeNode stack new StackTreeNode(); TreeNode cur root; while (cur ! null || stack.Count 0) { while (cur ! null) { stack.Push(cur); cur cur.left; } cur stack.Pop(); res.Add(cur.val); cur cur.right; } return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} stack : []*TreeNode{} cur : root for cur ! nil || len(stack) 0 { for cur ! nil { stack append(stack, cur) cur cur.Left } cur stack[len(stack)-1] stack stack[:len(stack)-1] res append(res, cur.Val) cur cur.Right } return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() val stack ArrayDequeTreeNode() var cur root while (cur ! null || stack.isNotEmpty()) { while (cur ! null) { stack.addLast(cur) cur cur.left } cur stack.removeLast() res.add(cur.val) cur cur.right } return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var stack [TreeNode]() var cur root while cur ! nil || !stack.isEmpty { while cur ! nil { stack.append(cur!) cur cur?.left } cur stack.removeLast() res.append(cur!.val) cur cur?.right } return res } }impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { while let Some(node) cur { stack.push(node.clone()); cur node.borrow().left.clone(); } let node stack.pop().unwrap(); res.push(node.borrow().val); cur node.borrow().right.clone(); } res } }仓库中的 python/0094-binary-tree-inorder-traversal.py 同时保留了递归与迭代两个版本迭代版本在文件前半部分其中迭代版本与上述 Python 代码逐行一致cpp/0094-binary-tree-inorder-traversal.cpp 也把递归版本注释在文件上方、迭代版本作为最终实现说明在实际刷题与面试场景中显式栈迭代是兼顾不爆栈与写法直观的折中选择。时间与空间复杂度时间复杂度$O(n)$每个节点入栈一次、出栈一次。空间复杂度栈最多同时容纳一条最左路径上的节点最坏情况为 $O(n)$输出数组额外占用 $O(n)$ 空间。解法三Morris 遍历O(1) 额外空间直觉递归和显式栈都至少需要 $O(h)$$h$ 为树高的辅助空间。Morris 遍历另辟蹊径临时修改树的结构——把左子树最右侧节点即当前节点的中序前驱的右指针临时指向当前节点形成一条线索thread。这样在遍历完左子树后不需要栈就能沿着线索回到当前节点处理完毕后把线索拆除恢复树的原始形态。算法步骤令当前节点cur root。当cur不为null时循环若cur没有左孩子将cur.val加入结果cur cur.right。否则在cur的左子树中找到最右侧节点prev即中序前驱若prev.right为null把prev.right指向cur建立线索然后cur cur.left。若prev.right已经指向cur说明左子树已遍历完拆除线索prev.right null将cur.val加入结果然后cur cur.right。返回结果列表。多语言实现class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: prev cur.left while prev.right and prev.right ! cur: prev prev.right if not prev.right: prev.right cur cur cur.left else: prev.right None res.append(cur.val) cur cur.right return respublic class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { prev.right cur; cur cur.left; } else { prev.right null; res.add(cur.val); cur cur.right; } } } return res; } }class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur) { if (!cur-left) { res.push_back(cur-val); cur cur-right; } else { TreeNode* prev cur-left; while (prev-right prev-right ! cur) { prev prev-right; } if (!prev-right) { prev-right cur; cur cur-left; } else { prev-right nullptr; res.push_back(cur-val); cur cur-right; } } } return res; } };class Solution { inorderTraversal(root) { const res []; let cur root; while (cur) { if (!cur.left) { res.push(cur.val); cur cur.right; } else { let prev cur.left; while (prev.right prev.right ! cur) { prev prev.right; } if (!prev.right) { prev.right cur; cur cur.left; } else { prev.right null; res.push(cur.val); cur cur.right; } } } return res; } }public class Solution { public Listint InorderTraversal(TreeNode root) { Listint res new Listint(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.Add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { prev.right cur; cur cur.left; } else { prev.right null; res.Add(cur.val); cur cur.right; } } } return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} cur : root for cur ! nil { if cur.Left nil { res append(res, cur.Val) cur cur.Right } else { prev : cur.Left for prev.Right ! nil prev.Right ! cur { prev prev.Right } if prev.Right nil { prev.Right cur cur cur.Left } else { prev.Right nil res append(res, cur.Val) cur cur.Right } } } return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() var cur root while (cur ! null) { if (cur.left null) { res.add(cur.val) cur cur.right } else { var prev cur.left while (prev?.right ! null prev.right ! cur) { prev prev.right } if (prev?.right null) { prev?.right cur cur cur.left } else { prev.right null res.add(cur.val) cur cur.right } } } return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var cur root while cur ! nil { if cur?.left nil { res.append(cur!.val) cur cur?.right } else { var prev cur?.left while prev?.right ! nil prev?.right ! cur { prev prev?.right } if prev?.right nil { prev?.right cur cur cur?.left } else { prev?.right nil res.append(cur!.val) cur cur?.right } } } return res } }// 说明Morris 遍历需要修改节点的右指针 // 在 Rust 的 RcRefCellTreeNode 共享所有权模型下不够地道 // 因此 LeetCode 的 Rust 版本通常采用上面解法二的显式栈实现。 impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { while let Some(node) cur { stack.push(node.clone()); cur node.borrow().left.clone(); } let node stack.pop().unwrap(); res.push(node.borrow().val); cur node.borrow().right.clone(); } res } }时间与空间复杂度时间复杂度$O(n)$。虽然寻找前驱时可能多次沿右指针下行但每条右链整体只会被走常数次摊还分析下总复杂度仍为 $O(n)$。空间复杂度仅 $O(1)$ 额外空间不含输出数组代价是遍历过程中临时修改了树的结构——这是它最大的特点也是它不适用于树不可变场景如 Rust 的RcRefCellTreeNode共享模型的原因。仓库源码对照同一道题多种语言风格除了上文已经对照过的 Python、C、Rust、TypeScript 实现仓库还提供了其他语言的同题解法适合横向对比不同语言的惯用写法语言仓库文件实现要点Cc/0094-binary-tree-inorder-traversal.c递归 手动malloc输出数组用int* returnSize记录已写入位置JavaScriptjavascript/0094-binary-tree-inorder-traversal.js递归 默认参数list []贯穿传递结果Gogo/0094-binary-tree-inorder-traversal.go切片模拟栈stack[:len(stack)-1]弹出栈顶Java / C# / Kotlin / Swiftjava/0094-*.java、csharp/0094-*.cs、kotlin/0094-*.kt、swift/0094-*.swift递归与迭代模板与上文一致仅语法层面差异以 C 版本为例c/0094-binary-tree-inorder-traversal.c它直接用递归fill_array填充预分配的数组文件头注释明确标注Space: O(n)、Time: O(n)是题目给定的returnSize指针 递归填表这一 C 语言题解惯用模式的完整示例可以帮助理解 C 接口中数组长度由调用方接收的约定。常见陷阱1. 递归中操作顺序写错中序遍历要求左 → 中 → 右。常见的错误是把res.append(node.val)放到两个递归调用之前或之后从而得到前序或后序遍历结果# 错误在 inorder(node.left) 之前就 res.append(node.val) # 正确先 inorder(node.left)再 res.append(node.val)判断标准很简单把当前节点的处理语句夹在两次递归调用中间就是中序放在最前面是前序放在最后面是后序。2. 迭代法忘记向右移动在迭代版本中弹出并处理完一个节点后必须执行cur cur.right。如果漏掉这一行cur会一直停留在同一个节点上导致死循环——因为外层while (cur || stack非空)的条件永远不会为假。3. 递归深度导致栈溢出当树严重不平衡例如退化为单链表时递归深度等于节点数可能触发系统调用栈溢出。此时应改用解法二的显式栈或在支持尾递归优化的场景下评估递归代价。中序遍历的实战应用BST 系列题的基石中序遍历在二叉搜索树问题中几乎无处不在仓库的 hints 目录与 articles 目录都能佐证这一点第 k 小元素kth-smallest-integer-in-bst的提示hints/kth-smallest-integer-in-bst.md明确指出利用 BST 结构做中序遍历先访问左子树保证先遇到较小节点再用计数器cnt追踪当前节点在升序序列中的位置当cnt k时记录并返回即可在 $O(n)$ 时间内找到第 k 小的整数。BST 合法性校验valid-binary-search-tree的提示hints/valid-binary-search-tree.md虽然推荐用区间约束[-infinity, infinity]逐层收窄做 DFS但中序遍历同样是一种经典判定手段——合法的 BST 中序遍历结果必然严格递增。树的还原articles/binary-tree-from-preorder-and-inorder-traversal.md 与 articles/construct-binary-tree-from-inorder-and-postorder-traversal.md 两篇题解展示了如何借助中序序列配合前序或后序序列重建整棵二叉树这在中序数组上定位根节点位置是关键步骤。理解了中序遍历升序输出这一核心性质你就能把这些看似独立的题目串成一条知识链达到一题会、百题通的效果。总结方案核心思想时间复杂度额外空间适用场景递归 DFS系统调用栈天然承载遍历顺序$O(n)$$O(h)$ 递归栈 $O(n)$ 输出写法最直观树高可控时优先迭代 DFS显式栈用栈模拟递归先深入左链再回头$O(n)$$O(h)$ 栈 $O(n)$ 输出树很高时避免递归爆栈Morris 遍历用前驱右指针建立临时线索遍历后拆除$O(n)$摊还$O(1)$ 额外空间空间敏感、允许临时修改树结构三者共享同一份左 → 中 → 右的语义差异只在于如何记住尚未处理的节点递归靠调用栈迭代靠显式栈Morris 靠树内线索。对照仓库中 articles/binary-tree-inorder-traversal.md 及python/0094-*、cpp/0094-*、c/0094-*、rust/0094-*等多语言实现建议在本地将三种写法各手写一遍并用[1, null, 2, 3]输出应为[1, 3, 2]、空树、单节点树、退化为链表的树等用例验证边界行为即可彻底掌握这道二叉树入门经典题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 94 二叉树中序遍历全解：递归、显式栈迭代与 Morris 遍历三方案（leetcode1 多语言源码对照）
LeetCode 94 二叉树中序遍历全解递归、显式栈迭代与 Morris 遍历三方案leetcode1 多语言源码对照【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode中序遍历Inorder Traversal以左子树 → 当前节点 → 右子树的顺序访问二叉树节点是深度优先搜索DFS的三种经典遍历之一对二叉搜索树BST而言中序遍历恰好输出递增有序序列因此它也是kth-smallest-integer-in-bst、valid-binary-search-tree等一批 BST 题目的解题基石。本文以仓库 articles/binary-tree-inorder-traversal.md 为骨架系统讲解递归、显式栈迭代、Morris 遍历三种实现方案并对照 python/0094-binary-tree-inorder-traversal.py、cpp/0094-binary-tree-inorder-traversal.cpp、c/0094-binary-tree-inorder-traversal.c、rust/0094-binary-tree-inorder-traversal.rs 等仓库源码帮你把这道题吃透到可以举一反三的程度。读完你将掌握三种写法的算法步骤、多语言实现与复杂度差异并能用中序遍历直接解决 BST 相关变体题。前置知识动手实现之前建议先确认自己熟悉以下三块基础二叉树结构理解节点如何通过left、right指针连接父子关系。仓库各语言题解文件开头都给出了对应语言的TreeNode定义例如 typescript/0094-binary-tree-inorder-traversal.ts 中的class TreeNode { val; left; right }c/0094-binary-tree-inorder-traversal.c 中对应的struct TreeNode。递归用递归调用天然地表达先左、再中、后右的遍历顺序递归深度即树高。栈Stack用显式栈模拟递归调用栈从而把递归写法改写成迭代写法避免递归深度过大时的栈溢出风险。解法一递归深度优先搜索Recursive DFS直觉中序遍历的访问顺序是固定的先左子树再当前节点最后右子树。递归函数天然携带当前子树根节点这一上下文因此只需要在递归函数中按这个顺序依次执行即可。对于二叉搜索树这一顺序会使输出的节点值严格递增——这正是中序这个名字的由来。算法步骤创建一个结果列表res用于存储节点值。定义递归辅助函数inorder(node)若node为null立即返回递归基。先递归调用inorder(node.left)遍历左子树。将当前节点值node.val追加到res。再递归调用inorder(node.right)遍历右子树。整棵树遍历完成后返回res。多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def inorder(node): if not node: return inorder(node.left) res.append(node.val) inorder(node.right) inorder(root) return respublic class Solution { private ListInteger res; public ListInteger inorderTraversal(TreeNode root) { res new ArrayList(); inorder(root); return res; } private void inorder(TreeNode node) { if (node null) { return; } inorder(node.left); res.add(node.val); inorder(node.right); } }class Solution { vectorint res; public: vectorint inorderTraversal(TreeNode* root) { inorder(root); return res; } private: void inorder(TreeNode* node) { if (!node) { return; } inorder(node-left); res.push_back(node-val); inorder(node-right); } };class Solution { inorderTraversal(root) { const res []; const inorder (node) { if (!node) return; inorder(node.left); res.push(node.val); inorder(node.right); }; inorder(root); return res; } }public class Solution { public Listint InorderTraversal(TreeNode root) { Listint res new Listint(); void Inorder(TreeNode node) { if (node null) return; Inorder(node.left); res.Add(node.val); Inorder(node.right); } Inorder(root); return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} var inorder func(node *TreeNode) inorder func(node *TreeNode) { if node nil { return } inorder(node.Left) res append(res, node.Val) inorder(node.Right) } inorder(root) return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() fun inorder(node: TreeNode?) { if (node null) return inorder(node.left) res.add(node.val) inorder(node.right) } inorder(root) return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() func inorder(_ node: TreeNode?) { guard let node node else { return } inorder(node.left) res.append(node.val) inorder(node.right) } inorder(root) return res } }impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); Self::inorder(root, mut res); res } fn inorder(node: OptionRcRefCellTreeNode, res: mut Veci32) { if let Some(n) node { let n n.borrow(); Self::inorder(n.left, res); res.push(n.val); Self::inorder(n.right, res); } } }仓库中 rust/0094-binary-tree-inorder-traversal.rs 就是这一递归思路的直接落地由于 Rust 采用RcRefCellTreeNode的共享所有权模型代码里通过v.borrow()获取节点可变内部值再递归访问v.left、v.right与上述伪代码完全对应。同理typescript/0094-binary-tree-inorder-traversal.ts 用默认参数list: Arraynumber []把结果数组一路向下传递本质上也是同一个递归模板。时间与空间复杂度时间复杂度$O(n)$其中 $n$ 为节点总数每个节点恰好被访问一次。空间复杂度递归调用栈深度取决于树高最坏情况退化为链表为 $O(n)$输出数组本身还需 $O(n)$ 空间。解法二迭代深度优先搜索Iterative DFS显式栈直觉递归依赖系统调用栈而我们可以用显式栈来模拟这一过程。核心技巧是尽可能向左深入把沿途经过的节点全部压栈当无法继续向左时从栈顶弹出一个节点处理然后转向它的右子树。栈的作用正是记住那些左子树处理完毕后还需要回头处理的节点。算法步骤初始化空的结果列表res和空栈stack。令当前节点cur root。当cur不为null或栈非空时循环只要cur不为null将cur压栈然后cur cur.left一路向左。从栈中弹出一个节点将其值加入res。令cur 弹出节点的右孩子。循环结束后返回res。多语言实现class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return respublic class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); StackTreeNode stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); res.add(cur.val); cur cur.right; } return res; } }class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stack; TreeNode* cur root; while (cur || !stack.empty()) { while (cur) { stack.push(cur); cur cur-left; } cur stack.top(); stack.pop(); res.push_back(cur-val); cur cur-right; } return res; } };class Solution { inorderTraversal(root) { const res []; const stack []; let cur root; while (cur || stack.length 0) { while (cur) { stack.push(cur); cur cur.left; } cur stack.pop(); res.push(cur.val); cur cur.right; } return res; } }public class Solution { public IListint InorderTraversal(TreeNode root) { Listint res new Listint(); StackTreeNode stack new StackTreeNode(); TreeNode cur root; while (cur ! null || stack.Count 0) { while (cur ! null) { stack.Push(cur); cur cur.left; } cur stack.Pop(); res.Add(cur.val); cur cur.right; } return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} stack : []*TreeNode{} cur : root for cur ! nil || len(stack) 0 { for cur ! nil { stack append(stack, cur) cur cur.Left } cur stack[len(stack)-1] stack stack[:len(stack)-1] res append(res, cur.Val) cur cur.Right } return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() val stack ArrayDequeTreeNode() var cur root while (cur ! null || stack.isNotEmpty()) { while (cur ! null) { stack.addLast(cur) cur cur.left } cur stack.removeLast() res.add(cur.val) cur cur.right } return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var stack [TreeNode]() var cur root while cur ! nil || !stack.isEmpty { while cur ! nil { stack.append(cur!) cur cur?.left } cur stack.removeLast() res.append(cur!.val) cur cur?.right } return res } }impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { while let Some(node) cur { stack.push(node.clone()); cur node.borrow().left.clone(); } let node stack.pop().unwrap(); res.push(node.borrow().val); cur node.borrow().right.clone(); } res } }仓库中的 python/0094-binary-tree-inorder-traversal.py 同时保留了递归与迭代两个版本迭代版本在文件前半部分其中迭代版本与上述 Python 代码逐行一致cpp/0094-binary-tree-inorder-traversal.cpp 也把递归版本注释在文件上方、迭代版本作为最终实现说明在实际刷题与面试场景中显式栈迭代是兼顾不爆栈与写法直观的折中选择。时间与空间复杂度时间复杂度$O(n)$每个节点入栈一次、出栈一次。空间复杂度栈最多同时容纳一条最左路径上的节点最坏情况为 $O(n)$输出数组额外占用 $O(n)$ 空间。解法三Morris 遍历O(1) 额外空间直觉递归和显式栈都至少需要 $O(h)$$h$ 为树高的辅助空间。Morris 遍历另辟蹊径临时修改树的结构——把左子树最右侧节点即当前节点的中序前驱的右指针临时指向当前节点形成一条线索thread。这样在遍历完左子树后不需要栈就能沿着线索回到当前节点处理完毕后把线索拆除恢复树的原始形态。算法步骤令当前节点cur root。当cur不为null时循环若cur没有左孩子将cur.val加入结果cur cur.right。否则在cur的左子树中找到最右侧节点prev即中序前驱若prev.right为null把prev.right指向cur建立线索然后cur cur.left。若prev.right已经指向cur说明左子树已遍历完拆除线索prev.right null将cur.val加入结果然后cur cur.right。返回结果列表。多语言实现class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: prev cur.left while prev.right and prev.right ! cur: prev prev.right if not prev.right: prev.right cur cur cur.left else: prev.right None res.append(cur.val) cur cur.right return respublic class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { prev.right cur; cur cur.left; } else { prev.right null; res.add(cur.val); cur cur.right; } } } return res; } }class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur) { if (!cur-left) { res.push_back(cur-val); cur cur-right; } else { TreeNode* prev cur-left; while (prev-right prev-right ! cur) { prev prev-right; } if (!prev-right) { prev-right cur; cur cur-left; } else { prev-right nullptr; res.push_back(cur-val); cur cur-right; } } } return res; } };class Solution { inorderTraversal(root) { const res []; let cur root; while (cur) { if (!cur.left) { res.push(cur.val); cur cur.right; } else { let prev cur.left; while (prev.right prev.right ! cur) { prev prev.right; } if (!prev.right) { prev.right cur; cur cur.left; } else { prev.right null; res.push(cur.val); cur cur.right; } } } return res; } }public class Solution { public Listint InorderTraversal(TreeNode root) { Listint res new Listint(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.Add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { prev.right cur; cur cur.left; } else { prev.right null; res.Add(cur.val); cur cur.right; } } } return res; } }func inorderTraversal(root *TreeNode) []int { res : []int{} cur : root for cur ! nil { if cur.Left nil { res append(res, cur.Val) cur cur.Right } else { prev : cur.Left for prev.Right ! nil prev.Right ! cur { prev prev.Right } if prev.Right nil { prev.Right cur cur cur.Left } else { prev.Right nil res append(res, cur.Val) cur cur.Right } } } return res }class Solution { fun inorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() var cur root while (cur ! null) { if (cur.left null) { res.add(cur.val) cur cur.right } else { var prev cur.left while (prev?.right ! null prev.right ! cur) { prev prev.right } if (prev?.right null) { prev?.right cur cur cur.left } else { prev.right null res.add(cur.val) cur cur.right } } } return res } }class Solution { func inorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var cur root while cur ! nil { if cur?.left nil { res.append(cur!.val) cur cur?.right } else { var prev cur?.left while prev?.right ! nil prev?.right ! cur { prev prev?.right } if prev?.right nil { prev?.right cur cur cur?.left } else { prev?.right nil res.append(cur!.val) cur cur?.right } } } return res } }// 说明Morris 遍历需要修改节点的右指针 // 在 Rust 的 RcRefCellTreeNode 共享所有权模型下不够地道 // 因此 LeetCode 的 Rust 版本通常采用上面解法二的显式栈实现。 impl Solution { pub fn inorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { while let Some(node) cur { stack.push(node.clone()); cur node.borrow().left.clone(); } let node stack.pop().unwrap(); res.push(node.borrow().val); cur node.borrow().right.clone(); } res } }时间与空间复杂度时间复杂度$O(n)$。虽然寻找前驱时可能多次沿右指针下行但每条右链整体只会被走常数次摊还分析下总复杂度仍为 $O(n)$。空间复杂度仅 $O(1)$ 额外空间不含输出数组代价是遍历过程中临时修改了树的结构——这是它最大的特点也是它不适用于树不可变场景如 Rust 的RcRefCellTreeNode共享模型的原因。仓库源码对照同一道题多种语言风格除了上文已经对照过的 Python、C、Rust、TypeScript 实现仓库还提供了其他语言的同题解法适合横向对比不同语言的惯用写法语言仓库文件实现要点Cc/0094-binary-tree-inorder-traversal.c递归 手动malloc输出数组用int* returnSize记录已写入位置JavaScriptjavascript/0094-binary-tree-inorder-traversal.js递归 默认参数list []贯穿传递结果Gogo/0094-binary-tree-inorder-traversal.go切片模拟栈stack[:len(stack)-1]弹出栈顶Java / C# / Kotlin / Swiftjava/0094-*.java、csharp/0094-*.cs、kotlin/0094-*.kt、swift/0094-*.swift递归与迭代模板与上文一致仅语法层面差异以 C 版本为例c/0094-binary-tree-inorder-traversal.c它直接用递归fill_array填充预分配的数组文件头注释明确标注Space: O(n)、Time: O(n)是题目给定的returnSize指针 递归填表这一 C 语言题解惯用模式的完整示例可以帮助理解 C 接口中数组长度由调用方接收的约定。常见陷阱1. 递归中操作顺序写错中序遍历要求左 → 中 → 右。常见的错误是把res.append(node.val)放到两个递归调用之前或之后从而得到前序或后序遍历结果# 错误在 inorder(node.left) 之前就 res.append(node.val) # 正确先 inorder(node.left)再 res.append(node.val)判断标准很简单把当前节点的处理语句夹在两次递归调用中间就是中序放在最前面是前序放在最后面是后序。2. 迭代法忘记向右移动在迭代版本中弹出并处理完一个节点后必须执行cur cur.right。如果漏掉这一行cur会一直停留在同一个节点上导致死循环——因为外层while (cur || stack非空)的条件永远不会为假。3. 递归深度导致栈溢出当树严重不平衡例如退化为单链表时递归深度等于节点数可能触发系统调用栈溢出。此时应改用解法二的显式栈或在支持尾递归优化的场景下评估递归代价。中序遍历的实战应用BST 系列题的基石中序遍历在二叉搜索树问题中几乎无处不在仓库的 hints 目录与 articles 目录都能佐证这一点第 k 小元素kth-smallest-integer-in-bst的提示hints/kth-smallest-integer-in-bst.md明确指出利用 BST 结构做中序遍历先访问左子树保证先遇到较小节点再用计数器cnt追踪当前节点在升序序列中的位置当cnt k时记录并返回即可在 $O(n)$ 时间内找到第 k 小的整数。BST 合法性校验valid-binary-search-tree的提示hints/valid-binary-search-tree.md虽然推荐用区间约束[-infinity, infinity]逐层收窄做 DFS但中序遍历同样是一种经典判定手段——合法的 BST 中序遍历结果必然严格递增。树的还原articles/binary-tree-from-preorder-and-inorder-traversal.md 与 articles/construct-binary-tree-from-inorder-and-postorder-traversal.md 两篇题解展示了如何借助中序序列配合前序或后序序列重建整棵二叉树这在中序数组上定位根节点位置是关键步骤。理解了中序遍历升序输出这一核心性质你就能把这些看似独立的题目串成一条知识链达到一题会、百题通的效果。总结方案核心思想时间复杂度额外空间适用场景递归 DFS系统调用栈天然承载遍历顺序$O(n)$$O(h)$ 递归栈 $O(n)$ 输出写法最直观树高可控时优先迭代 DFS显式栈用栈模拟递归先深入左链再回头$O(n)$$O(h)$ 栈 $O(n)$ 输出树很高时避免递归爆栈Morris 遍历用前驱右指针建立临时线索遍历后拆除$O(n)$摊还$O(1)$ 额外空间空间敏感、允许临时修改树结构三者共享同一份左 → 中 → 右的语义差异只在于如何记住尚未处理的节点递归靠调用栈迭代靠显式栈Morris 靠树内线索。对照仓库中 articles/binary-tree-inorder-traversal.md 及python/0094-*、cpp/0094-*、c/0094-*、rust/0094-*等多语言实现建议在本地将三种写法各手写一遍并用[1, null, 2, 3]输出应为[1, 3, 2]、空树、单节点树、退化为链表的树等用例验证边界行为即可彻底掌握这道二叉树入门经典题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
