樹遍歷得到節點和路徑的子節點

Question

假設我們有一棵高度不同的樹的多個節點。 是否有任何有效的方法來獲取節點的子節點和根路徑？ 這意味着我們可以得到所有節點，低於我們的節點集，但是到頂部我們只想要父母，直到我們到達根。 （我們不希望父母的孩子）。 由於樹可能會變得非常巨大，我們想要根據我們是哪個節點來懶惰地加載孩子。提前致謝。

Answer 1

取決於約束條件，有多種方法，首先可以爲O（N + M）中的每個節點預先計算此值。但是如果樹很大，那麼你不能真正存儲這些值。因此，有第二種方法，很容易找到從每個節點到節點的路徑（對於每個節點，您將只保留關於父節點的信息）。對於孩子們來說，你可以存儲預先遍歷的節點，並且在節點和節點之間的所有內容都將成爲你的問題的答案。整體複雜度應該是O（N + M）