tree - 树遍历的时间复杂度是多少？

Question

树遍历的时间复杂度是多少，我敢肯定它一定很明显，但我可怜的大脑现在无法计算出来。

Answer 1

这取决于您执行的遍历类型和算法，但通常是 O(n)，其中 n 是树中节点的总数。深度优先遍历的规范递归实现将按照最深级别的顺序消耗内存（在堆栈上），在平衡树上它将是 log(n)。

Answer 2

对于具有n 个节点的树来说，这不只是n吗？

你参观每片树叶一次，不是吗？所以我会说它是线性的。