京公网安备11010502063487号给定一棵二叉树的根结点，返回它的中序遍历：先遍历左子树，再访问根结点，最后遍历右子树。递归写法只有三行，是每个人写的第一个树算法。但它有一个隐蔽的限制：递归深度等于树的高度，对于退化成链的树，深度可以是 n，在 Python 里默认递归上限 1000 层，树一深就会栈溢出。迭代写法用一个显式的栈：一路向左走到底并把沿途结点压栈，然后弹出栈顶访问，再转向它的右子树。本文用真实运行展示递归写法在深链上崩溃、迭代写法不受影响，用 Morris 遍历验证 O(1) 额外空间的做法结果一致，给出五种语言的实现，并把栈的变化做成分步演示（这是本系列第一个用到二叉树面板的演示）。
完整题目见官方页面（链接在文末）。树在测试里用 LeetCode 的层序数组表示：按层从左到右列出结点，用 null 表示空位，结果数组是遍历得到的结点值序列。基准解是递归写法（先左、再根、再右）。一共 12 组用例，覆盖：官方示例、空树、单个结点、只有左孩子的链、只有右孩子的链、完全二叉树、含空位的不规则树：
输入 [[1,null,2,3]] 输出 [1,3,2] 输入 [[]] 输出 [] 输入 [[1]] 输出 [1] 输入 [[1,2,3,4,5,null,8,null,null,6,7,9]] 输出 [4,2,6,5,7,1,3,9,8] 输入 [[3,2,null,1]] 输出 [1,2,3] 输入 [[1,null,2,null,3]] 输出 [1,2,3]
对一棵只有左孩子的链，深度等于结点数 n。Python 的递归写法在 n 超过默认上限（1000）时就会抛出 RecursionError，而用显式栈的迭代写法没有这个限制（栈是堆上的列表）。下面是真实运行的结果：
深度为 n 的左斜链：递归写法 vs 迭代写法（Python 默认递归深度上限 1000） n= 500: 递归 成功（500 个） 迭代 成功（500 个，0.07 ms） n= 900: 递归 成功（900 个） 迭代 成功（900 个，0.11 ms） n= 1100: 递归 RecursionError 迭代 成功（1100 个，0.13 ms） n= 5000: 递归 RecursionError 迭代 成功（5000 个，0.47 ms） n=100000: 递归 RecursionError 迭代 成功（100000 个，4.31 ms）
n = 500、900 时递归写法可以完成；n = 1100 就失败了（每层递归本身还要占一点额外的栈帧，所以在 1000 附近就撑不住了）；迭代写法在 n = 100000 时也只需要 4.31ms。Java、C++ 也有栈深度限制（默认线程栈大小限定），只是上限的数值不同，这里没有另外实测。
Morris 遍历不用栈也不用递归：利用树里空闲的右指针，临时把"中序前驱结点的右指针"指向当前结点（线索化），走完之后再恢复。额外空间是 O(1)。我在 Python 里实现了它，并在 20000 棵随机树上验证了它与栈迭代的结果完全一致：
随机 20000 棵树：Morris 遍历（O(1) 额外空间）与栈迭代的结果全部一致：True
Morris 遍历会临时修改树的结构，遍历结束后恢复；如果遍历中途出错，树会处于被修改的状态，所以本文的主要解法仍然选择栈迭代。
cur 指向当前结点。循环条件是 cur 非空或者栈非空：内层循环让 cur 一路向左，沿途把结点压栈（它们要等左子树访问完才轮到自己）；左边走到头之后，弹出栈顶，它就是当前最左的、左子树已经访问完的结点，访问它（把值加入结果）；然后让 cur 指向它的右孩子，继续同样的过程。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；测试程序把层序数组建成真正的结点对象再调用（建树的代码不属于解法本身）。
Python · 解法代码class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def inorder_traversal(root): res, st = [], [] cur = root while cur or st: while cur: # 一路向左走到底，沿途的结点都压栈（它们要等左子树访问完才轮到自己） st.append(cur) cur = cur.left cur = st.pop() # 栈顶就是当前最左边、左子树已经访问完的结点 res.append(cur.val) # 访问它 cur = cur.right # 再去处理它的右子树 return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,null,2,3]] → [1,3,2] [[]] → [] [[1]] → [1] [[1,2,3,4,5,null,8,null,null,6,7,9]] → [4,2,6,5,7,1,3,9,8] [[3,2,null,1]] → [1,2,3] [[1,null,2,null,3]] → [1,2,3]
Java · 解法代码class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } } class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> st = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !st.isEmpty()) { while (cur != null) { // 一路向左走到底，沿途的结点都压栈 st.push(cur); cur = cur.left; } cur = st.pop(); // 栈顶就是当前最左边、左子树已经访问完的结点 res.add(cur.val); // 访问它 cur = cur.right; // 再去处理它的右子树 } return res; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,null,2,3]] → [1,3,2] [[]] → [] [[1]] → [1] [[1,2,3,4,5,null,8,null,null,6,7,9]] → [4,2,6,5,7,1,3,9,8] [[3,2,null,1]] → [1,2,3] [[1,null,2,null,3]] → [1,2,3]
Go · 解法代码type TreeNode struct { Val int Left, Right *TreeNode } func inorderTraversal(root *TreeNode) []int { res := []int{} st := []*TreeNode{} cur := root for cur != nil || len(st) > 0 { for cur != nil { // 一路向左走到底，沿途的结点都压栈 st = append(st, cur) cur = cur.Left } cur = st[len(st)-1] // 栈顶就是当前最左边、左子树已经访问完的结点 st = st[:len(st)-1] res = append(res, cur.Val) // 访问它 cur = cur.Right // 再去处理它的右子树 } return res }
$ go build -o bin . && ./bin < cases.jsonl [[1,null,2,3]] → [1,3,2] [[]] → [] [[1]] → [1] [[1,2,3,4,5,null,8,null,null,6,7,9]] → [4,2,6,5,7,1,3,9,8] [[3,2,null,1]] → [1,2,3] [[1,null,2,null,3]] → [1,2,3]
JavaScript · 解法代码class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function inorderTraversal(root) { const res = [], st = []; let cur = root; while (cur || st.length > 0) { while (cur) { // 一路向左走到底，沿途的结点都压栈 st.push(cur); cur = cur.left; } cur = st.pop(); // 栈顶就是当前最左边、左子树已经访问完的结点 res.push(cur.val); // 访问它 cur = cur.right; // 再去处理它的右子树 } return res; }
$ node run.js < cases.jsonl [[1,null,2,3]] → [1,3,2] [[]] → [] [[1]] → [1] [[1,2,3,4,5,null,8,null,null,6,7,9]] → [4,2,6,5,7,1,3,9,8] [[3,2,null,1]] → [1,2,3] [[1,null,2,null,3]] → [1,2,3]
C++ · 解法代码#include <vector> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; vector<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { // 一路向左走到底，沿途的结点都压栈 st.push_back(cur); cur = cur->left; } cur = st.back(); // 栈顶就是当前最左边、左子树已经访问完的结点 st.pop_back(); res.push_back(cur->val); // 访问它 cur = cur->right; // 再去处理它的右子树 } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,null,2,3]] → [1,3,2] [[]] → [] [[1]] → [1] [[1,2,3,4,5,null,8,null,null,6,7,9]] → [4,2,6,5,7,1,3,9,8] [[3,2,null,1]] → [1,2,3] [[1,null,2,null,3]] → [1,2,3]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和递归写法做了随机对拍：结点数 0 到 12 的随机二叉树（左右子树的大小随机划分）：
随机对拍 20000 组（结点数 0 到 12 的随机二叉树（左右子树大小随机划分，结点值取 0 到 5 起递增的数）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题每个结点只被访问一次，是线性的，所以没有做规模对比实验。
下面的演示用树 [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]，结点 1 是根。蓝色是 cur 指向的结点，绿色是已访问的结点，右边的栈是"等着被访问的结点"，栈顶在最上面。可以看到：一路向左压入 1、2、4；4 没有左孩子，弹出并访问 4；然后转向它的右子树（空），再弹出栈顶 2……最后结果是 [4, 2, 6, 5, 7, 1, 3, 9, 8]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。