LeetCode 386中等DFS/字典序
字典序排数 图解题解
这道题到底在问什么
给定整数 n，返回 1 到 n 按字典序(按字符串比较)排序的列表。要求时间 O(n)、不真的去排序。
- 输入
- n=13
- 输出
- [1,10,11,12,13,2,3,4,5,6,7,8,9]
- 输入
- n=2
- 输出
- [1,2]
最优解：一步一步想明白
- 3核心一句话:字典序 = 数字树上的前序遍历。记住「先收当前数、再按 0..9 下探孩子、越过 n 就回退」，下面每帧都在套它。
- 4准备 · 结果为空开局结果为空,调用栈也是空的。外层循环让 1 到 9 依次当根做前序 DFS。先从 1 开始。
- 5访问 1进入 dfs(1)。前序的第一步:先把当前数 1(紫色)收进结果列表。它现在排在第 1 位。
- 6下探 1 → 101 的孩子 10(在 1 末尾接一位 0)不超过 n=11，前序要先走完这一支,递归进 dfs(10)。
- 7访问 10进入 dfs(10)。前序的第一步:先把当前数 10(紫色)收进结果列表。它现在排在第 2 位。
- 8孩子 100 越界轮到 10 的孩子 100(=10*10+0)，它 > n=11，越界。10 后面更大的孩子(101..109)只会更大，全部跳过。
- 9回退离开 1010 的孩子都试完了，dfs(10) 结束,回退到父亲 1，继续试 1 的下一个孩子。
- 10下探 1 → 111 的孩子 11(在 1 末尾接一位 1)不超过 n=11，前序要先走完这一支,递归进 dfs(11)。
- 11访问 11进入 dfs(11)。前序的第一步:先把当前数 11(紫色)收进结果列表。它现在排在第 3 位。
- 12孩子 110 越界轮到 11 的孩子 110(=11*10+0)，它 > n=11，越界。11 后面更大的孩子(111..119)只会更大，全部跳过。
- 13回退离开 1111 的孩子都试完了，dfs(11) 结束,回退到父亲 1，继续试 1 的下一个孩子。
- 14孩子 12 越界轮到 1 的孩子 12(=1*10+2)，它 > n=11，越界。1 后面更大的孩子(13..19)只会更大，全部跳过。
- 15回退离开 11 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 2 重新开始。
- 16根 1 这一支完成根 1 的整棵数字子树(1 → 10 → 11)前序走完了，结果已是 [1, 10, 11]。接着轮到根 2。注意 10、11 都排在 2 前面，这正是字典序。
- 17访问 2进入 dfs(2)。前序的第一步:先把当前数 2(紫色)收进结果列表。它现在排在第 4 位。
- 18孩子 20 越界轮到 2 的孩子 20(=2*10+0)，它 > n=11，越界。2 后面更大的孩子(21..29)只会更大，全部跳过。
- 19回退离开 22 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 3 重新开始。
- 20访问 3进入 dfs(3)。前序的第一步:先把当前数 3(紫色)收进结果列表。它现在排在第 5 位。
- 21孩子 30 越界轮到 3 的孩子 30(=3*10+0)，它 > n=11，越界。3 后面更大的孩子(31..39)只会更大，全部跳过。
- 22回退离开 33 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 4 重新开始。
- 23访问 4进入 dfs(4)。前序的第一步:先把当前数 4(紫色)收进结果列表。它现在排在第 6 位。
- 24孩子 40 越界轮到 4 的孩子 40(=4*10+0)，它 > n=11，越界。4 后面更大的孩子(41..49)只会更大，全部跳过。
- 25回退离开 44 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 5 重新开始。
- 26访问 5进入 dfs(5)。前序的第一步:先把当前数 5(紫色)收进结果列表。它现在排在第 7 位。
- 27孩子 50 越界轮到 5 的孩子 50(=5*10+0)，它 > n=11，越界。5 后面更大的孩子(51..59)只会更大，全部跳过。
- 28回退离开 55 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 6 重新开始。
- 29访问 6进入 dfs(6)。前序的第一步:先把当前数 6(紫色)收进结果列表。它现在排在第 8 位。
- 30孩子 60 越界轮到 6 的孩子 60(=6*10+0)，它 > n=11，越界。6 后面更大的孩子(61..69)只会更大，全部跳过。
- 31回退离开 66 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 7 重新开始。
- 32访问 7进入 dfs(7)。前序的第一步:先把当前数 7(紫色)收进结果列表。它现在排在第 9 位。
- 33孩子 70 越界轮到 7 的孩子 70(=7*10+0)，它 > n=11，越界。7 后面更大的孩子(71..79)只会更大，全部跳过。
- 34回退离开 77 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 8 重新开始。
- 35访问 8进入 dfs(8)。前序的第一步:先把当前数 8(紫色)收进结果列表。它现在排在第 10 位。
- 36孩子 80 越界轮到 8 的孩子 80(=8*10+0)，它 > n=11，越界。8 后面更大的孩子(81..89)只会更大，全部跳过。
- 37回退离开 88 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 9 重新开始。
- 38访问 9进入 dfs(9)。前序的第一步:先把当前数 9(紫色)收进结果列表。它现在排在第 11 位。
- 39孩子 90 越界轮到 9 的孩子 90(=9*10+0)，它 > n=11，越界。9 后面更大的孩子(91..99)只会更大，全部跳过。
- 40回退离开 99 这一支整棵子树都走完了。外层根 1 到 9 已全部处理完，准备收束输出答案。
- 41完成1 到 11 在数字树上前序遍历完毕，结果 [1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9] 正好是字典序:10、11 紧跟在 1 后面(它们都以 1 开头)，2 才接在后面。全程没有真的去排序，一次 DFS 直接走出有序结果。
⚠️ 容易写错的地方
✗ 错：把 1..n 转字符串再 sort
✓ 对：用数字树前序 DFS 直接走出有序
排序是 O(n log n),本题要的是不排序的 O(n)
✗ 错：孩子从 d=1 接、根从 0 起
✓ 对：孩子从 d=0 接到 9,根只能 1 到 9
漏 d=0 会丢掉 10 这类数,而 0 不在范围且无前导 0
✗ 错：某孩子越界后还试更大的孩子
✓ 对：越界即停本层后续孩子
x*10+d 随 d 递增,一个越界后面必然也越界
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
ans = []
def dfs(x):
if x > n:
return
ans.append(x)
for d in range(10):
child = x * 10 + d
if child > n:
break
dfs(child)
for x in range(1, 10):
dfs(x)
return ansC++
#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ans;
function<void(int)> dfs = [&](int x) {
if (x > n) return;
ans.push_back(x);
for (int d = 0; d <= 9; ++d) {
int child = x * 10 + d;
if (child > n) break;
dfs(child);
}
};
for (int x = 1; x <= 9; ++x) dfs(x);
return ans;
}
};Java
import java.util.*;
class Solution {
List<Integer> ans;
int n;
public List<Integer> lexicalOrder(int n) {
this.n = n; ans = new ArrayList<>();
for (int x = 1; x <= 9; x++) dfs(x);
return ans;
}
private void dfs(int x) {
if (x > n) return;
ans.add(x);
for (int d = 0; d <= 9; d++) {
int child = x * 10 + d;
if (child > n) break;
dfs(child);
}
}
}复杂度
时间
O(n)
数字树上每个不超过 n 的数恰好被访问一次,共 n 个节点;越界的孩子一判即回,均摊 O(1)
空间
O(log n)
递归栈深 = 最大数字的位数 = O(log₁₀ n);不计输出列表本身
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字典序排数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果不允许用递归(怕栈溢出),怎么写迭代版?+
用一个当前数 cur(从 1 开始),每步决定往哪走:① 能下探就 cur*=10(末尾接 0);② 否则若 cur 末位不是 9 且 cur+1 ≤ n 就 cur+=1(同层下一个);③ 否则不断 cur/=10 退回上层,直到 cur 末位不是 9 再 cur+=1。每访问一个就记录,直到收满 n 个。这是把递归 DFS 改写成「在数字树上手动走指针」,空间 O(1)。
为什么这题要求 O(n) 而不能直接排序?+
排序是 O(n log n)、还要把所有数转成字符串占额外空间。本题的考点正是发现「字典序 = 数字树前序」这层结构,用一次 DFS 在 O(n) 内不排序地走出有序结果,体现对字典序本质的理解。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 字典序排数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。