解題說明
Lexicographical Numbers
題目描述：給定整數 n，請回傳 1 到 n 之間所有整數的字典序排列。例如 n = 13，字典序為 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]。要求時間複雜度 O(n)，空間複雜度 O(log n)（不計輸出）。
解題思路：將 1 到 n 的所有數字想像成一棵 10 叉 Trie（字典樹），每個節點代表一個數字前綴，根節點的子節點為 19，每個節點的子節點是原數字後接 09。字典序遍歷等同於對這棵 Trie 做前序 DFS。
無需實際建構 Trie，直接用一個游標 cur 模擬 DFS 過程：
- 優先向「子節點」走：若
cur * 10 <= n，則進入cur * 10（相當於在數字後補 0，往更深一層走）。 - 無法繼續往下時，向「兄弟節點」走：
cur++；若cur超過 n 或末位進位（cur % 10 == 0），需退回父節點再往右（cur /= 10，再cur++，直到cur % 10 != 0）。 - 每次停留在某個節點時，將
cur記錄進答案。
這樣一次線性掃描即可按字典序收集所有數字，無需排序。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個數字恰好被訪問一次，總迴圈次數等於 n。
空間複雜度：O(log n) — 不計輸出陣列，游標變數僅需常數空間；若將遞迴 DFS 版本的呼叫堆疊納入考量，遞迴深度為 O(log₁₀ n)（即數字位數）。
虛擬碼
1. Initialize cur = 1, result = [].
2. While len(result) < n:
a. Append cur to result.
b. If cur * 10 <= n: cur = cur * 10 (go to first child).
c. Else:
- If cur >= n: cur = cur / 10 (step back before incrementing).
- cur = cur + 1 (move to next sibling).
- While cur % 10 == 0: cur = cur / 10 (undo trailing zeros / backtrack).
3. Return result.其他解法
方法二：直接排序字串
將 1 到 n 轉換成字串後排序，利用 C++ std::sort 的預設字典序比較，最後轉回整數。時間 O(n log n · d)（d 為數字位數），空間 O(n · d)。實作簡單，但效率遠低於 DFS 模擬，且空間消耗更大，不符合題目要求。
方法三：遞迴 DFS
對每個起始點 1~9 遞迴 DFS，對節點 cur 先記錄，再遞迴子節點 cur*10 到 cur*10+9（不超過 n）。邏輯與迴圈版本等價，但有函式呼叫開銷，遞迴深度 O(log n)。適合理解思路，但因遞迴開銷略遜於迴圈版本。
方法四：Trie 樹建構
顯式建構 10 叉 Trie，插入 1 到 n 的所有數字，再前序遍歷輸出。時間 O(n · d)，空間 O(n · d)（n 個節點，每層最多 10 個子節點）。概念最直觀但空間浪費最嚴重，不推薦用於此題。
延伸思考
- 若要求字典序第 k 小的數字（即 LC 440），不輸出所有數字只找單一答案，如何在 O((log n)²) 時間內解決？
- 若數字範圍改為 1 到 n 的所有偶數，字典序輸出規則如何改變？DFS 模擬需要做哪些調整？
- 此題的 DFS 模擬等同於對 Trie 做前序遍歷，若改成中序或後序遍歷 Trie，對應的輸出順序有何意義？