美团算法专项面经：二叉树遍历、栈与队列、贪心算法、字符串匹配

上篇聊完架构设计，这篇回到算法。美团算法面试中等偏上，Medium题要求思路清晰、代码无Bug、复杂度分析到位。Android岗集中在树、栈/队列、贪心和字符串匹配，不考图论和高级DP，但手写代码要能跑通。

今天8道题覆盖美团算法核心考点，每道给出思路+代码+复杂度。

Q1：二叉树的前中后序遍历？迭代怎么写？

递归写法简单：前序（根→左→右）、中序（左→根→右）、后序（左→右→根）。三行代码搞定。

迭代写法（面试常考）：用栈模拟递归。

前序迭代：根入栈，循环弹栈处理 → 右子入栈 → 左子入栈（栈后进先出，左子先处理）。

List<Integer> preorder(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if (root != null) stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return