在二叉树的第N层中找到第k个节点。

Question

给定一棵二叉树，如果父节点为0，则左子节点为0，右子节点为1。如果父节点为1，则左子节点为1，右子节点为0。根节点为0。找到第N层中存在的第k个节点值。

我尝试用以下方法解决。假设第一层有0，第二层有01，第三层有01-10（即前一半的补集）。类似地，第四层上是0110 1001。

现在如何推广这个解决方案或其他解决问题的方法？

- user650521

Answer 1

为了概括您的想法，您可以编写一个递归过程，给出树的第n个级别元素的列表，因为（正如您所说）每个级别都可以通过连接上一级及其补集来获得：

getLevel(level)

  if level == 0
    return [0]

  upperLevel = getLevel(level - 1)

  return upperLevel + complement(upperLevel)

[...] 是一个列表，+ 表示连接多个列表，而 complement 的作用是将 0 转化为 1，将 1 转化为 0。

有了这些，你只需要获取 getLevel(n) 生成的列表中第 k 个元素即可。

这可能不是最优解，只是基于你的想法建立起来的（并且比较容易实现）。

- effeffe

Answer 2

我手动生成了前几位，并得到了0110100110010110。谷歌显示这是Thue-Morse序列。在OEIS中，序列A010060的注释中有以下一行：

a(n) = S2(n) mod 2，其中S2(n) = n的二进制表示法下每一位数字之和。

这里的n就是你的情况下的k，而你的情况中N并不重要。因此，要确定a(n)，需要计算n中1的数量，并取该总和的最低有效位。

- Dialecticus