在由 1 到 (2^K) 的每个数字填充的完整 BST 中查找缺失值，其中 K 是级别数

Question

令 K 为二叉搜索树的层数。因此，我可以拥有的最大节点数是 (2^K)-1。我有一个完整的二叉树（即，每个级别都被完全填充），其节点填充有从 1 到 (2^k) 的每个值，没有重复。由于有 (2^K)-1 个可用节点需要填充，但有 2^K 个可用值，因此二叉搜索树中必定缺少 1 到 (2^K) 之间的一个值。 帮我设计一个算法来查找缺失值。时间复杂度应该是O(K)。本质上，只需遍历每个级别一次。

提前致谢！

这是我的 DSA 作业问题之一。我使用中序遍历有一个很好的实现，但这不是 O(K)，而是 O(2^K)/O(n)。我只是不确定这在 O(K) 时间复杂度中是否可行。

例如，对于 K=4，我用 1 到 2^4=16 之间的值填充二叉树。但只有 15 个节点，因此遗漏了 1 个。在下面的示例中，我省略了 14。如何在 O(K) 时间内检测到 14 丢失了？

            8                          k=1
          /   \
         4     12                      k=2
        / \    /  \
      2    6   10   15                k=3
     / \  / \  / \   / \
     1 3  5 7 9  11 13 16             k=4 

Answer 1

下面的伪代码是不言自明的，并且它的运行时间显然是 O(K):

findMissing(node)
  if isLeaf(node) {
    if node.value % 2 == 0
      return node.value - 1
    else
      return node.value + 1
  }
  else {
    if node.value % 2 == 0
      return findMissing(node.rightChild)
    else
      return findMissing(node.leftChild)
  }

直觉是，给定固定的 K，树中的每个节点只能有两个可能的值。例如，当K=4时，根可以是8或9，最左边的叶子可以是1或2等。 因此，我们可以利用节点值的奇偶性来猜测哪棵子树是“不平衡”的。