在内存有限的二叉树中查找第一个null [英] Find first null in binary tree with limited memory

问题描述

我有一棵二叉树，每个节点可以有一个值.

I have a binary tree where each node can have a value.

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

I want to find the node in the tree that has value null and is closest to the root. If there are two nodes with the same distance from the root, either will do. I need to minimize the number of read accesses to the binary tree. Assume that working memory is limited to just k nodes.

深度为k的DFS详尽无遗，但除非我先遍历整个树，否则将找不到最接近的节点. BFS会找到最接近的空值，但可能会失败，因为DFS可以找到具有相同内存的更深的空值.

DFS to depth k is exhaustive but will not find the closest node unless I run through the whole tree first. BFS will find the closest, but it might fail because DFS can find deeper nulls with the same memory.

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

I'd like to have the fewest number of read accesses to the tree and find the closest null node.

(我最终也将需要在n路树中实现这一点，所以一般的解决方案将是一个好办法.对树没有写访问权，只能读.)

(I'll need to implement this in n-way trees eventually, too, so a general solution would be good. No write access to the tree, just read.)

推荐答案

您可能想看看迭代加深深度优先搜索.它会自动找到最近的节点，但能够达到与DFS相同的深度.但是它将使用更多的读取访问权限.

You may want to look at Iterative-deepening depth-first search. It will find the closest node automatically but will be able to reach the same depth as DFS. It will use more read accesses though.

您也可以从BFS开始，如果在允许的内存中找不到空值，请运行DFS.

You could also start with BFS, and if you don't find a null with the allowed memory, run DFS.

这篇关于在内存有限的二叉树中查找第一个null的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！