迭代深化首先使用有限的内存搜索

Question

这是Find first null in binary tree with limited memory的后续行动。

维基百科说，迭代加深深度优先搜索将找到最短路径。我想要一个内存限制为k个节点的实现，并且访问树的次数最少。

举例来说，如果我的二叉树是：

  0 
    1    2 
3 4  5  6 
7 8 9 10 11 12 13 14 

而且我有限的内存比我的搜索顺序5个节点是：

mem[0] = read node 0 
mem[1] = read node 1 
mem[2] = read node 2 
mem[3] = read node 3 
mem[4] = read node 4 //Now my memory is full. I continue... 
mem[3] = read node 5 //overwrite where I stored node 3 
mem[4] = read node 6 //overwrite where I stored node 4 

现在，如果我的下一个读是7，我需要重新阅读3.但是，如果我将下一个阅读到14，那么我不需要重新阅读3。如果解决方案是在14，这将使我的算法快一点！

我正在寻找一个通用的解决方案;可以用于任何大小的内存和每个节点的分支数量。

Answer 1

如果您的节点链接到其父母，并且节点的子节点将始终按照相同的顺序枚举，则可以在不保存节点的情况下跟踪您的步骤。