查找二叉树第N层中的kth节点

Question

可能重复： 堆树中的k元素

给定二叉树，如果父树为0，则左子为0，右子为1。如果父母为1，则左子为1，右子为0。树的根是0。查找Nth级别上存在的kth节点值。

我试着用这种方式解决问题。假设第一级有0，第二级有01，第三级有01 - 10 (即前半部分的补充)。

同样，0110 1001在第四层。

现在，我如何概括这个解决方案或任何其他方法来解决这个问题？

Answer 1

我手动生成了前几位，得到了0110100110010110位。谷歌透露这是Thue-Morse序列。在OEIS中序列A010060。在OEIS页面上的评论如下：

a(n) = S2(n) mod 2，其中S2(n) = n，n在基-2表示法中的数字之和。

在这里，n是您的例子中的k，而N在您的情况下并不重要。因此，确定a(n)在n中计算1的个数，并且取这个和中最不重要的一点。