题目描述
思路解析动画文字版
核心一句话:字典序 = 数字树上的前序遍历。记住「先收当前数、再按 0..9 下探孩子、越过 n 就回退」，下面每帧都在套它。
开局结果为空,调用栈也是空的。外层循环让 1 到 9 依次当根做前序 DFS。先从 1 开始。
进入 dfs(1)。前序的第一步:先把当前数 1(紫色)收进结果列表。它现在排在第 1 位。
1 的孩子 10(在 1 末尾接一位 0)不超过 n=11，前序要先走完这一支,递归进 dfs(10)。
进入 dfs(10)。前序的第一步:先把当前数 10(紫色)收进结果列表。它现在排在第 2 位。
轮到 10 的孩子 100(=10*10+0)，它 > n=11，越界。10 后面更大的孩子(101..109)只会更大，全部跳过。
10 的孩子都试完了，dfs(10) 结束,回退到父亲 1，继续试 1 的下一个孩子。
1 的孩子 11(在 1 末尾接一位 1)不超过 n=11，前序要先走完这一支,递归进 dfs(11)。
进入 dfs(11)。前序的第一步:先把当前数 11(紫色)收进结果列表。它现在排在第 3 位。
轮到 11 的孩子 110(=11*10+0)，它 > n=11，越界。11 后面更大的孩子(111..119)只会更大，全部跳过。
11 的孩子都试完了，dfs(11) 结束,回退到父亲 1，继续试 1 的下一个孩子。
轮到 1 的孩子 12(=1*10+2)，它 > n=11，越界。1 后面更大的孩子(13..19)只会更大，全部跳过。
1 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 2 重新开始。
根 1 的整棵数字子树(1 → 10 → 11)前序走完了，结果已是 [1, 10, 11]。接着轮到根 2。注意 10、11 都排在 2 前面，这正是字典序。
进入 dfs(2)。前序的第一步:先把当前数 2(紫色)收进结果列表。它现在排在第 4 位。
轮到 2 的孩子 20(=2*10+0)，它 > n=11，越界。2 后面更大的孩子(21..29)只会更大，全部跳过。
2 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 3 重新开始。
进入 dfs(3)。前序的第一步:先把当前数 3(紫色)收进结果列表。它现在排在第 5 位。
轮到 3 的孩子 30(=3*10+0)，它 > n=11，越界。3 后面更大的孩子(31..39)只会更大，全部跳过。
3 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 4 重新开始。
进入 dfs(4)。前序的第一步:先把当前数 4(紫色)收进结果列表。它现在排在第 6 位。
轮到 4 的孩子 40(=4*10+0)，它 > n=11，越界。4 后面更大的孩子(41..49)只会更大，全部跳过。
4 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 5 重新开始。
进入 dfs(5)。前序的第一步:先把当前数 5(紫色)收进结果列表。它现在排在第 7 位。
轮到 5 的孩子 50(=5*10+0)，它 > n=11，越界。5 后面更大的孩子(51..59)只会更大，全部跳过。
5 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 6 重新开始。
进入 dfs(6)。前序的第一步:先把当前数 6(紫色)收进结果列表。它现在排在第 8 位。
轮到 6 的孩子 60(=6*10+0)，它 > n=11，越界。6 后面更大的孩子(61..69)只会更大，全部跳过。
6 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 7 重新开始。
进入 dfs(7)。前序的第一步:先把当前数 7(紫色)收进结果列表。它现在排在第 9 位。
轮到 7 的孩子 70(=7*10+0)，它 > n=11，越界。7 后面更大的孩子(71..79)只会更大，全部跳过。
7 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 8 重新开始。
进入 dfs(8)。前序的第一步:先把当前数 8(紫色)收进结果列表。它现在排在第 10 位。
轮到 8 的孩子 80(=8*10+0)，它 > n=11，越界。8 后面更大的孩子(81..89)只会更大，全部跳过。
8 这一支整棵子树都走完了，回到最外层循环,准备从下一个根 9 重新开始。
进入 dfs(9)。前序的第一步:先把当前数 9(紫色)收进结果列表。它现在排在第 11 位。
轮到 9 的孩子 90(=9*10+0)，它 > n=11，越界。9 后面更大的孩子(91..99)只会更大，全部跳过。
9 这一支整棵子树都走完了。外层根 1 到 9 已全部处理完，准备收束输出答案。
1 到 11 在数字树上前序遍历完毕，结果 [1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9] 正好是字典序:10、11 紧跟在 1 后面(它们都以 1 开头)，2 才接在后面。全程没有真的去排序，一次 DFS 直接走出有序结果。
边界先想清:n 很小的时候孩子大多越界,DFS 退化成几乎只访问根;但 10 这种「以 1 开头」的数仍会紧跟 1。
面试两个高频追问:迭代版怎么走指针、以及为什么坚持 O(n) 不排序。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(n)，数字树上每个不超过 n 的数恰好被访问一次,共 n 个节点;越界的孩子一判即回,均摊 O(1)
- 空间：O(log n)，递归栈深 = 最大数字的位数 = O(log₁₀ n);不计输出列表本身
易错点
面试追问把动画讲成自己的话
追问如果不允许用递归(怕栈溢出),怎么写迭代版?
追问为什么这题要求 O(n) 而不能直接排序?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题