树遍历得到节点和路径的子节点

Question

假设我们有一棵高度不同的树的多个节点。 是否有任何有效的方法来获取节点的子节点和根路径？ 这意味着我们可以得到所有节点，低于我们的节点集，但是到顶部我们只想要父母，直到我们到达根。 （我们不希望父母的孩子）。 由于树可能会变得非常巨大，我们想要根据我们是哪个节点来懒惰地加载孩子。提前致谢。

Answer 1

取决于约束条件，有多种方法，首先可以为O（N + M）中的每个节点预先计算此值。但是如果树很大，那么你不能真正存储这些值。因此，有第二种方法，很容易找到从每个节点到节点的路径（对于每个节点，您将只保留关于父节点的信息）。对于孩子们来说，你可以存储预先遍历的节点，并且在节点和节点之间的所有内容都将成为你的问题的答案。整体复杂度应该是O（N + M）