Recursive Java Solution using pre-order traversal

  • 6

    The big idea is Tree's pre-order traversal, which means we first output the root, and then its left and right child, and we cannot output right child until we finishing outputting all nodes on the left branch.
    For this problem, a dummy node is the top root, and its children are 1 through 9; for node 1, its children are 10, 100, 1000 and so on; for node 10, its children are 11 through 19.
    Notes that we use (i + 1 <= (i / 10) * 10 + 9) to restrict the range of children.

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>();
            lexicalOrderHelper(res, 1, n);
            return res;
        private void lexicalOrderHelper(List<Integer> res, int i, int n) {
            if(i > n) return;
            lexicalOrderHelper(res, i * 10, n);
            if(i + 1 <= (i / 10) * 10 + 9) lexicalOrderHelper(res, i + 1, n);
            else return;

  • 1

    I was trying to solve this in DFS but not have clear mind before I read your post. clever to think in a pre-order traversal way

    while the code is very clear, explanation is a little confusing.

    Tell by the code, each node has two children
    left : curVal*10

    right : curVal+1 under condition specified in your code

    by pre-order, after add cur, we first try left then go right.

  • 0

    @三千世界 Generally, each node do have more than two nodes. This code does not show you how to build the Tree, but tell you how to traverse the Tree.

  • 0

    Do you know the complexity of your code?

  • 0

    @eraman664 time complexity is O(n), space complexity for stack call is O(log_10(9n+1)), this is a complete 10-nary tree

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.