JAVA Solution with a map to record the uncomplete subtree then DFS

• ``````   /**
* for each subtree if it is complete tree
* then the num of child is 11111....
* so first find the root of each layer which is uncomplete and record the numbers of child
*/
public int findKthNumber(int n, int k) {
int cur = 1;
k = k - 1;
int layer = (int)Math.log10(n);
int seg = 0;
for (int i = 0 ; i <= layer; i ++) {
seg += Math.pow(10, i);
}
Map<Integer, Integer> map = new HashMap<>();
map.put(n, 1);
int cu = n / 10;
int va = n % 10;
map.put(cu, va + map.get(n)+1);
gettheUncompletelyWay(cu , map);
//calculate the D_value of root cur and cur + 1;
while (k > 0) {
int Dvalue;
if (map.containsKey(cur)) {
Dvalue = map.get(cur);
if (k >= Dvalue) {
cur += 1;
k -= Dvalue;
}else {
cur *= 10;
k -= 1;
}
seg = (seg - 1)/10;
}else {
Dvalue = seg;
if (k >= Dvalue) {
cur += 1;
k -= Dvalue;
}else {
cur *= 10;
k -= 1;
seg = (seg - 1)/10;
}
}
}
return cur;
}

//get the way that is consist of each root of uncomplete tree and the number of child
//using map dp solution
private void gettheUncompletelyWay(int n, Map<Integer, Integer> map) {
int t = 11;
int pre = 1;
while (n >= 10) {
int cu = n / 10;
int va = n % 10;
map.put(cu, va * t + map.get(n)+ (10 - va - 1) * pre + 1);
pre = t;
t = t * 10 + 1;
n = cu;
}
}
``````

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