企业官网建设流程全解析

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）

直觉

中序遍历的访问顺序是固定的：先左子树，再当前节点，最后右子树。递归函数天然携带"当前子树根节点"这一上下文，因此只需要在递归函数中按这个顺序依次执行即可。对于二叉搜索树，这一顺序会使输出的节点值严格递增——这正是"中序"这个名字的由来。

算法步骤

1. 创建一个结果列表res，用于存储节点值。
2. 定义递归辅助函数inorder(node)：
3. 若node为null，立即返回（递归基）。
4. 先递归调用inorder(node.left)遍历左子树。
5. 将当前节点值node.val追加到res。
6. 再递归调用inorder(node.right)遍历右子树。
7. 整棵树遍历完成后返回res。

多语言实现

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # 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 res

public class Solution { private List<Integer> res; public List<Integer> 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 { vector<int> res; public: vector<int> 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 List<int> InorderTraversal(TreeNode root) { List<int> res = new List<int>(); 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?): List<Int> { val res = mutableListOf<Int>() 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: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut res = Vec::new(); Self::inorder(&root, &mut res); res } fn inorder(node: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) { 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 采用Rc<RefCell<TreeNode>>的共享所有权模型，代码里通过v.borrow()获取节点可变内部值，再递归访问v.left、v.right，与上述伪代码完全对应。同理，typescript/0094-binary-tree-inorder-traversal.ts 用默认参数list: Array<number> = []把结果数组一路向下传递，本质上也是同一个递归模板。

时间与空间复杂度

• 时间复杂度：$O(n)$，其中 $n$ 为节点总数，每个节点恰好被访问一次。
• 空间复杂度：
  • 递归调用栈深度取决于树高，最坏情况（退化为链表）为 $O(n)$；
  • 输出数组本身还需 $O(n)$ 空间。

解法二：迭代深度优先搜索（Iterative DFS，显式栈）

直觉

递归依赖系统调用栈，而我们可以用显式栈来模拟这一过程。核心技巧是：尽可能向左深入，把沿途经过的节点全部压栈；当无法继续向左时，从栈顶弹出一个节点处理，然后转向它的右子树。栈的作用正是"记住那些左子树处理完毕后还需要回头处理的节点"。

算法步骤

1. 初始化空的结果列表res和空栈stack。
2. 令当前节点cur = root。
3. 当cur不为null或栈非空时循环：
   • 只要cur不为null：将cur压栈，然后cur = cur.left（一路向左）。
   • 从栈中弹出一个节点，将其值加入res。
   • 令cur = 弹出节点的右孩子。
4. 循环结束后返回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 res

public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> 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: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> 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 IList<int> InorderTraversal(TreeNode root) { List<int> res = new List<int>(); Stack<TreeNode> stack = new Stack<TreeNode>(); 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?): List<Int> { val res = mutableListOf<Int>() val stack = ArrayDeque<TreeNode>() 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: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut res = Vec::new(); let mut stack: Vec<Rc<RefCell<TreeNode>>> = 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）。这样在遍历完左子树后，不需要栈就能沿着线索回到当前节点；处理完毕后把线索拆除，恢复树的原始形态。

算法步骤

1. 令当前节点cur = root。
2. 当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。
3. 返回结果列表。

多语言实现

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 res

public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> 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: vector<int> inorderTraversal(TreeNode* root) { vector<int> 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 List<int> InorderTraversal(TreeNode root) { List<int> res = new List<int>(); 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?): List<Int> { val res = mutableListOf<Int>() 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 的 Rc<RefCell<TreeNode>> 共享所有权模型下不够地道， // 因此 LeetCode 的 Rust 版本通常采用上面"解法二"的显式栈实现。 impl Solution { pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut res = Vec::new(); let mut stack: Vec<Rc<RefCell<TreeNode>>> = 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 的Rc<RefCell<TreeNode>>共享模型）的原因。

仓库源码对照：同一道题，多种语言风格

除了上文已经对照过的 Python、C++、Rust、TypeScript 实现，仓库还提供了其他语言的同题解法，适合横向对比不同语言的惯用写法：

以 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 两篇题解展示了如何借助中序序列（配合前序或后序序列）重建整棵二叉树，这在中序数组上定位根节点位置是关键步骤。

理解了中序遍历"升序输出"这一核心性质，你就能把这些看似独立的题目串成一条知识链，达到"一题会、百题通"的效果。

总结

三者共享同一份"左 → 中 → 右"的语义，差异只在于"如何记住尚未处理的节点"：递归靠调用栈，迭代靠显式栈，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