一、题目描述给定一个二叉树的根节点root返回它的中序遍历 结果。中序遍历顺序左子树 → 根节点 → 右子树示例输入root [1,null,2,3] 输出[1,3,2]输入root [] 输出[]输入root [1] 输出[1]二、为什么这题“看起来简单但值得深究”如果你熟悉递归这题一句话就能写完先遍历左子树再访问根再遍历右子树。但问题是递归写法真的理解了吗能不能用 O(1) 额外空间不算递归栈完成面试官会不会让你写迭代版 所以我们必须从递归 → 迭代 → Morris 遍历 逐层推进。三、核心思想中序遍历的本质1️⃣ 递归视角最直观中序遍历的规则是固定的inorder(root): inorder(left) visit(root) inorder(right)递归之所以成立是因为二叉树天然具有子问题结构每一棵子树都满足同样的遍历规则2️⃣ 迭代视角显式栈递归本质上使用的是系统调用栈。如果我们手动维护一个栈一路向左走到底弹栈访问节点转向右子树 这就是中序遍历的迭代写法。3️⃣ Morris 遍历O(1) 额外空间Morris 遍历的核心思想是利用二叉树中原本为 null 的指针临时建立“线索”遍历完成后再恢复结构。它不需要栈也不修改节点 val只调整指针。四、解法一递归最推荐面试首选思路左子树根右子树Java 实现class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); inorder(root, res); return res; } private void inorder(TreeNode node, ListInteger res) { if (node null) return; inorder(node.left, res); res.add(node.val); inorder(node.right, res); } }复杂度分析指标数值时间复杂度O(n)空间复杂度O(h)递归栈h 为树高✅面试时90% 情况写到这就够了。五、解法二迭代显式栈核心流程当前节点一直向左走沿途入栈弹栈访问节点转向右子树重复步骤 1Java 实现class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); DequeTreeNode stack new ArrayDeque(); 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; } }复杂度分析指标数值时间复杂度O(n)空间复杂度O(h)✅适合面试官追问“不用递归怎么写”的场景。六、解法三Morris 中序遍历O(1) 空间核心思想如果左子树为空访问当前节点走向右子树如果左子树不为空找到左子树中最右的节点前驱将其right指向当前节点当前节点移向左子树当第二次回到当前节点时恢复指针并访问Java 实现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 pre cur.left; while (pre.right ! null pre.right ! cur) { pre pre.right; } if (pre.right null) { pre.right cur; cur cur.left; } else { pre.right null; res.add(cur.val); cur cur.right; } } } return res; } }复杂度分析指标数值时间复杂度O(n)空间复杂度O(1) ✅✅这是真正的“不借助栈、O(1) 空间”解法。七、三种解法对比总结解法是否推荐空间复杂度面试评价递归⭐⭐⭐⭐⭐O(h)最常用最安全迭代⭐⭐⭐⭐O(h)展示基本功Morris⭐⭐⭐O(1)高级加分项八、面试高频追问❓为什么中序遍历是有序的✅ 因为 BST 的中序遍历天然递增。❓递归和迭代哪个更好✅ 面试先写递归再补迭代。❓Morris 遍历会破坏树结构吗✅ 不会指针会被恢复。九、一句话总结递归写左中右迭代显式用栈Morris 借指针中序遍历不再难。
