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

Question

树遍历的时间复杂度是多少，我敢肯定它必须很明显，但是我可怜的大脑现在无法解决。

Answer 1

它取决于您执行哪种遍历以及算法，但是通常它将是O(n)，其中n是树中节点的总数。深度优先遍历的规范递归实现将以最深级别的顺序(在堆栈上)消耗内存，而在平衡树上则为log(n)。