可能重复：堆树中的第K个元素
给定二叉树，如果父级为0，则左子级为0，右子级为1.如果父级为1，则左子级为1，右子级为0.如果父级为0，则查找第k个节点值出现在第N级
我试着用这种方式解决 . 假设第一级有 0 ，第二级有 01 ，第三级有 01 - 10 （即上半部分的补码） .同样 0110 1001 在第四级 .
0
01
01 - 10
0110 1001
现在，我如何概括这个解决方案或任何其他方式来解决这个问题？
为了概括你的想法，你可以编写一个递归过程，给出树的第n级元素的列表，因为（就像你说的）每个级别都可以获得连接上层和它的补码：
getLevel(level) if level == 0 return [0] upperLevel = getLevel(level - 1) return upperLevel + complement(upperLevel)
其中 [...] 是一个列表， + 是列表的串联， complement 将 0 更改为 1 ，反之亦然 .
[...]
+
complement
1
有了这个，你只需得到 getLevel(n) 生成的列表的 k 元素 .
getLevel(n)
k
这可能不是最佳解决方案，它只是 Build 在你的想法上（而且很容易） .
我手动生成了前几位，并获得了0110100110010110.Google显示这是Thue-Morse sequence . 在OEIS中序列A010060 . 对OEIS页面的评论有以下几行：
a（n）= S2（n）mod 2，其中S2（n）=基数为2的符号中n，n的数字之和 .
在这里 n 是你的情况是 k ，在你的情况下 N 并不重要 . 因此，要确定（n）在 n 中计算1的数量，并取此总和的最低有效位 .
n
N
2 回答
为了概括你的想法，你可以编写一个递归过程，给出树的第n级元素的列表，因为（就像你说的）每个级别都可以获得连接上层和它的补码：
其中
[...]是一个列表，+是列表的串联，complement将0更改为1，反之亦然 .有了这个，你只需得到
getLevel(n)生成的列表的k元素 .这可能不是最佳解决方案，它只是 Build 在你的想法上（而且很容易） .
我手动生成了前几位，并获得了0110100110010110.Google显示这是Thue-Morse sequence . 在OEIS中序列A010060 . 对OEIS页面的评论有以下几行：
a（n）= S2（n）mod 2，其中S2（n）=基数为2的符号中n，n的数字之和 .
在这里
n是你的情况是k，在你的情况下N并不重要 . 因此，要确定（n）在n中计算1的数量，并取此总和的最低有效位 .