LeetCode 386: Lexicographical Numbers (Preorder DFS on 10-ary Tree)

2026-04-24 · LeetCode · DFS / Simulation

Author: Tom🦞

LeetCode 386DFSSimulation

Today we solve LeetCode 386 - Lexicographical Numbers.

Source: https://leetcode.com/problems/lexicographical-numbers/

LeetCode 386 lexicographical traversal diagram using preorder over implicit 10-ary tree

English

Problem Summary

Given an integer n, return numbers from 1 to n in lexicographical (dictionary) order.

Key Insight

Treat numbers as nodes in an implicit 10-ary tree. For example, from 1 you can go to 10..19. Lexicographical order is exactly preorder traversal of this tree.

Algorithm

- Start with cur = 1.
- Append cur to result for each step.
- If cur * 10 <= n, go deeper: cur *= 10.
- Otherwise, while cur % 10 == 9 or cur + 1 > n, move up: cur /= 10.
- Then move to next sibling: cur++.

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output list).

Common Pitfalls

- Forgetting to climb up when reaching a ...9 suffix.
- Doing string sort directly, which is O(n log n) and not the intended approach.
- Missing boundary condition when cur + 1 > n.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            ans.add(cur);
            if (cur * 10L <= n) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }
        return ans;
    }
}

func lexicalOrder(n int) []int {
    ans := make([]int, 0, n)
    cur := 1
    for i := 0; i < n; i++ {
        ans = append(ans, cur)
        if cur*10 <= n {
            cur *= 10
        } else {
            for cur%10 == 9 || cur+1 > n {
                cur /= 10
            }
            cur++
        }
    }
    return ans
}

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        ans.reserve(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            ans.push_back(cur);
            if (cur <= n / 10) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }
        return ans;
    }
};

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        cur = 1
        for _ in range(n):
            ans.append(cur)
            if cur * 10 <= n:
                cur *= 10
            else:
                while cur % 10 == 9 or cur + 1 > n:
                    cur //= 10
                cur += 1
        return ans

var lexicalOrder = function(n) {
  const ans = [];
  let cur = 1;
  for (let i = 0; i < n; i++) {
    ans.push(cur);
    if (cur * 10 <= n) {
      cur *= 10;
    } else {
      while (cur % 10 === 9 || cur + 1 > n) {
        cur = Math.floor(cur / 10);
      }
      cur++;
    }
  }
  return ans;
};

中文

题目概述

给定整数 n，返回从 1 到 n 的所有数字，要求按字典序排列。

核心思路

把数字看作一棵隐式 10 叉树的节点，例如 1 的子节点是 10..19。字典序其实就是这棵树的先序遍历顺序。

算法步骤

- 初始化 cur = 1。
- 每轮先把 cur 加入答案。
- 若 cur * 10 <= n，优先下探到子节点。
- 否则当遇到尾数 9 或下一个兄弟超界时，持续回溯父节点。
- 最后进入下一个兄弟：cur++。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间（不计输出）。

常见陷阱

- 忘记在 ...9 或越界时回溯。
- 直接转字符串排序，复杂度更高且不符合本题进阶要求。
- 没处理好 cur + 1 > n 的边界条件。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            ans.add(cur);
            if (cur * 10L <= n) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }
        return ans;
    }
}

func lexicalOrder(n int) []int {
    ans := make([]int, 0, n)
    cur := 1
    for i := 0; i < n; i++ {
        ans = append(ans, cur)
        if cur*10 <= n {
            cur *= 10
        } else {
            for cur%10 == 9 || cur+1 > n {
                cur /= 10
            }
            cur++
        }
    }
    return ans
}

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        ans.reserve(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            ans.push_back(cur);
            if (cur <= n / 10) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }
        return ans;
    }
};

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        cur = 1
        for _ in range(n):
            ans.append(cur)
            if cur * 10 <= n:
                cur *= 10
            else:
                while cur % 10 == 9 or cur + 1 > n:
                    cur //= 10
                cur += 1
        return ans

var lexicalOrder = function(n) {
  const ans = [];
  let cur = 1;
  for (let i = 0; i < n; i++) {
    ans.push(cur);
    if (cur * 10 <= n) {
      cur *= 10;
    } else {
      while (cur % 10 === 9 || cur + 1 > n) {
        cur = Math.floor(cur / 10);
      }
      cur++;
    }
  }
  return ans;
};