求字符 ‘a’ 和 ‘b’ 组成的，最大长度为n的字符串中字典序第 k 个字符串

先来解释一下这个题目，假设最大长度为3，那么由字符a和b组成的字符串有：

a, b, ab, aaa, aba...

把这些字符串按照字典序排序:

1. a
2. aa
3. aaa
4. aab
5. ab
6. aba
7. abb
8. b
9. ba
10. baa
11. bab
12. bb
13. bba
14. bbb

由于只有两个字符，可以用前缀树来存储所有的字符串，对于n=2时的前缀树：

既然用到了树数据结构，这里可以用回溯法的思想来解决这道问题，先遍历左子节点，即先获取字符a，然后再遍历右子节点，即获取字符b
代码如下:

java">public class KLenString{public static boolean found;public static int k;public static String result;public static void backtrace(StringBuilder sb, int depth){if(found){return;}if(sb.length() > 0){k--;if(k == 0){result = sb.toString();found = true;return;}}if(sb.length() == depth){return;}sb.append('a');backtrace(sb, depth);sb.deletCharAt(sb.length()-1);sb.append('b');backtrace(sb, depth);sb.deletCharAt(sb.length()-1);}
}