algorithm - 是否有固定内存使用的树遍历算法？

Question

我有树的第一个节点。类似的东西:

class TreeNode {
   int uniqueValue;
   List<TreeNode> children;
}

我想找到最节省内存的方法来打印树的所有节点。树可能很大或很大。它可以很深也可以很宽。我知道递归和堆栈的算法。我想找到的是独立于图形大小使用固定内存量的算法。

树不是二叉树!

Answer 1

没有这样的 O(1) 算法。最坏情况下的内存使用总是 O(N)。您可以通过添加字段来“欺骗”以支持直接遍历到图形节点。这样，如果您能够将图形加载到内存中，您就可以遍历它(使用 BFS 或 DFS)。