我有一个二叉树，其中每个节点都可以有一个值。
我想在树中找到值为 null 并且最接近根的节点。如果有两个节点与根的距离相同，则任何一个都可以。我需要最小化对二叉树的读取访问次数。假设工作记忆仅限于 k 个节点。
DFS 到深度 k 是详尽的，但除非我先遍历整个树，否则不会找到最近的节点。BFS 会找到最接近的，但它可能会失败，因为 DFS 可以使用相同的内存找到更深的空值。
我希望对树的读取访问次数最少，并找到最近的空节点。
（我最终也需要在 n 路树中实现这一点，所以一个通用的解决方案会很好。没有对树的写访问权限，只是读取。）
我将通过简单的树修剪来实现 DFS。所以，你必须运行整个树是不正确的。
例如，如果您在高度 h 处找到了一个空值，则可以跳过位于相同或更深位置的节点。
您可能想查看迭代加深深度优先搜索。它将自动找到最近的节点，但能够达到与 DFS 相同的深度。不过，它将使用更多的读取访问。
您也可以从 BFS 开始，如果在允许的内存中找不到 null，请运行 DFS。
如果您无法更改数据结构，那么您将不得不读取每个节点 - 广度优先。
如果可以更改数据结构，则每个节点都可以记录第一个空子节点的相对深度。（每个都从其孩子的等效值中计算出来）。
然后你知道在寻找最早的空值时要追查树中的哪一行。
如果您愿意将树存储在数组中，有一种简单的方法。不是每个节点都有指向其左右子节点的指针，而是节点 n 的子节点是数组中的 2n + 1 和 2n + 2。（并且节点 n 的父节点是 (n-1)/2，如果 n != 0。）
Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};
简单地线性迭代数组就相当于一个 BFS，但空间要求为 O(1)。
这可以很容易地扩展到 n 叉树。例如，在三叉树中，左孩子是 3n+1，中心是 3n+2，右孩子是 3n+3，如果 n !=0，则父母是 (n-1)/3。