<分区>
Possible Duplicate:
K-th element in a heap tree
给定一棵二叉树，如果父为0，则左子为0，右子为1。如果父为1，则左子为1，右子为0。树的根为0。找到第k个第 N 层的节点值
我试过这样解决。假设第一层有 0，第二层有 01，第三层有 01 - 10(即上半部分的补码)。
同样在第四层 0110 1001。
现在我如何概括这个解决方案或任何其他方法来解决这个问题？
<分区>
Possible Duplicate:
K-th element in a heap tree
给定一棵二叉树，如果父为0，则左子为0，右子为1。如果父为1，则左子为1，右子为0。树的根为0。找到第k个第 N 层的节点值
我试过这样解决。假设第一层有 0，第二层有 01，第三层有 01 - 10(即上半部分的补码)。
同样在第四层 0110 1001。
现在我如何概括这个解决方案或任何其他方法来解决这个问题？
最佳答案
为了概括您的想法，您可以编写一个递归过程，给出树的第 nth 层的元素列表，因为(如您所说)每个层都可以通过连接上层及其补充:
getLevel(level)
if level == 0
return [0]
upperLevel = getLevel(level - 1)
return upperLevel + complement(upperLevel)
其中[...]是一个列表，+是列表的串联，补充改变0 进入 1，反之亦然。
有了这个，您只需获取 getLevel(n) 生成的列表的第 kth 元素。
这可能不是最佳解决方案，它只是建立在您的想法之上(而且很简单)。
关于algorithm - 在第 N 层二叉树中找到第 k 个节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13938830/