binary-tree - 在内存有限的二叉树中找到第一个空值

Question

我有一个二叉树，其中每个节点都可以有一个值。

我想在树中找到值为 null 并且最接近根的节点。如果有两个节点与根的距离相同，则任一个都可以。我需要尽量减少对二叉树的读取访问次数。假设工作内存仅限于 k 个节点。

DFS 到深度 k 是详尽的，但除非我先遍历整棵树，否则不会找到最近的节点。 BFS 会找到最接近的，但它可能会失败，因为 DFS 可以使用相同的内存找到更深的空值。

我希望对树的读取访问次数最少，并找到最近的空节点。

(我最终也需要在 n-way 树中实现它，所以一般的解决方案会很好。没有对树的写访问权限，只需读取。)

Answer 1

我将通过简单的树修剪来实现 DFS。所以，你必须运行整棵树是不正确的。例如，如果您在高度 h 处定位了空值，则可以跳过位于相同或更深位置的节点。