- 正确答案：中序遍历二叉树的顺序是“左子树 → 根节点 → 右子树”。递归实现的核心逻辑是：先递归遍历左子树，再访问当前节点（如打印值或加入结果列表），最后递归遍历右子树。非递归实现则借助显式栈模拟调用栈行为：从根开始，持续向左下压栈直至空节点；弹出栈顶作为当前访问节点并记录其值；然后转向该节点的右子树，重复上述过程。 - 解答思路：面试官要求“手撕”，意味着需现场写出可运行、边界完备、风格清晰的代码。应优先给出递归解法（简洁、符合定义、易理解），再主动补充非递归解法（体现对栈机制和执行流程的底层掌握）。需明确说明两种方法的时间/空间复杂度，并指出递归隐含系统栈、非递归使用手动栈的本质区别。关键边界处理包括：空树（root == null）直接返回；单节点树需正确输出该节点值；避免空指针访问（如访问node.left前判空在非递归中非必须，因循环内已做null检查）。 - 深度知识讲解：中序遍历本质是二叉搜索树（BST）的自然排序序列——若一棵二叉树是BST，则其中序遍历结果严格升序。这源于BST定义：左子树所有节点值 < 根值 < 右子树所有节点值，而中序“左-根-右”恰好按数值从小到大线性展开。因此，中序遍历是验证BST、查找第k小元素、实现迭代器（如Java的TreeSet遍历）、以及将BST转为有序链表等场景的基础原语。从编译原理视角看，中序遍历对应表达式树的中缀表达式生成（如树节点为操作符/操作数，中序输出即带括号的a + b * c）。递归实现的底层是函数调用栈：每次递归调用push一个栈帧，保存当前node、执行位置（如“刚返回左子树，下一步要访问根”）、局部变量；当node为null时触发回溯（pop）。非递归栈中存储的是“待继续处理的根节点”，栈中元素始终代表尚未访问根节点及其右子树的入口点，而左子路径已被完全展开并压栈。进阶考点常延伸至Morris遍历（O(1)空间）：利用叶子节点的空右指针临时指向中序前驱，形成线索化结构，遍历后恢复树结构。其核心是两次遍历同一边：第一次建立线索，第二次利用线索访问并拆除。这要求深刻理解中序前驱定义（左子树最右节点，或无左子树时向上找第一个“左孩子路径包含当前节点”的祖先）。 - 递归代码（Java）： public List inorderTraversal(TreeNode root) { List res = new ArrayList<>(); inorder(root, res); return res; } private void inorder(TreeNode node, List res) { if (node == null) return; inorder(node.left, res); // 左 res.add(node.val); // 根 inorder(node.right, res); // 右 } - 非递归代码（Java，显式栈）： public List inorderTraversal(TreeNode root) { List res = new ArrayList<>(); Stack stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 沿左链向下，压入所有左节点（不含null） while (cur != null) { stack.push(cur); cur = cur.left; } // 弹出栈顶，即最左未访问节点 cur = stack.pop(); res.add(cur.val); // 访问根 cur = cur.right; // 转向右子树 } return res; } - Morris遍历伪代码（O(1)空间，仅作知识扩展）： function morrisInorder(root): res = [] cur = root while cur != null: if cur.left == null: res.append(cur.val) cur = cur.right else: // 找cur的中序前驱（左子树最右节点） prev = cur.left while prev.right != null and prev.right != cur: prev = prev.right if prev.right == null: // 前驱未线索化：建立线索，向左走 prev.right = cur cur = cur.left else: // 前驱已线索化：访问cur，拆除线索，向右走 prev.right = null res.append(cur.val) cur = cur.right return res

AI应用开发实习一面分享Momenta

全站热榜

创作者周榜