二叉树用深度遍历好还是层次遍历好?

结论：没有“绝对更好”，按任务选。两者时间复杂度都是 O(n)，关键差在**内存占用与是否需要层级信息**。 # 速选 * 需要“最近/最浅”的答案（最小深度、最近满足条件的节点、无权最短路径）：\*\*层次遍历（BFS）\*\*更好，一层层推进，先命中最浅解。 * 需要按固定顺序处理或易于剪枝（如表达式求值、构建/验证 BST、区间剪枝）：\*\*深度优先遍历（DFS：前/中/后序）\*\*更好，路径局部性强、易剪枝。 * 输出按“层”的结果（层序列表、右视图、连接同层 next 指针）：**BFS**更直接。 * BST 要有序输出：**中序 DFS**天然升序。 * 树很“宽”（接近满二叉树）：**DFS**更省内存（BFS 队列可能接近 n/2）。 * 树很“深且瘦”（长链状）：避免递归 DFS（可能栈溢出），用**迭代 DFS**或选 BFS。 # 复杂度与内存 * BFS：时间 O(n)；空间 O(w)，w 为最大层宽。满二叉树 w≈n/2，可能占用较大内存。 * DFS：时间 O(n)；空间 O(h)，h 为高度。平衡树 h≈log n，链状树 h≈n（递归易栈溢出，迭代更安全）。 # Java 模板 层次遍历（BFS，按层收集）： ```java List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { int size = q.size(); List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i++) { TreeNode n = q.poll(); level.add(n.val); if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right); } res.add(level); } return res; } ``` 深度优先（DFS）常见三种顺序： * 前序：根→左→右（构建/拷贝树、序列化常用） * 中序：左→根→右（BST 升序） * 后序：左→右→根（删除/释放、表达式求值） 递归前序： ```java void preorder(TreeNode r, List<Integer> out) { if (r == null) return; out.add(r.val); preorder(r.left, out); preorder(r.right, out); } ``` 迭代前序（避免递归栈）： ```java List<Integer> preorderIter(TreeNode root) { List<Integer> out = new ArrayList<>(); Deque<TreeNode> st = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !st.isEmpty()) { while (cur != null) { out.add(cur.val); st.push(cur); cur = cur.left; } cur = st.pop().right; } return out; } ``` # 实战建议 * 做“最近/最浅/层级类”题：BFS。 * 做“路径/剪枝/有序输出/构造或评估表达式”题：DFS（尽量迭代版，避免深递归）。 * 工程里若只是遍历做统计，两者皆可；优先选**更易表达业务逻辑**的那一个，并关注内存峰值（宽树用 DFS、更深的树用迭代 DFS）。