【十叉树的先序遍历】字典序的第K小数字

求解代码

publicintfindKthNumber(intn,intk){intcur=1;// 从字典序第一个数字 1 开始k--;// 转换为 0 索引while(k>0){// 计算以cur为根的子树，包含的有效节点数量intsteps=getSteps(cur,n);if(steps<=k){// 目标不在当前子树，跳过整棵子树，更新k和当前节点k-=steps;cur++;}else{// 目标在子树中，进入子节点，k减1（跳过当前节点）cur*=10;k--;}}returncur;}// 计算以cur为根节点的子树中，<=n的节点总数privateintgetSteps(intcur,longn){intsteps=0;longfirst=cur;// 当前层起始节点longlast=cur;// 当前层结束节点while(first<=n){// 累加当前层的节点数，防止last超出nsteps+=Math.min(last,n)-first+1;// 进入下一层first*=10;last=last*10+9;}returnsteps;}

小贴士

• k--是为了将1-based的输入转换为0-based计数
• first/last必须用long类型，避免int乘法溢出；