树遍历的时间复杂度是多少? [英] What is the time complexity of tree traversal?
本文介绍了树遍历的时间复杂度是多少?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
树遍历的时间复杂度是多少，我确定它一定很明显，但我可怜的大脑现在无法解决.
What is the time complexity of tree traversal, I'm sure it must be obvious but my poor brain can not work it out right now.
推荐答案
这取决于您正在执行的遍历类型和算法，但通常是 O(n)，其中 n 是树中的节点总数.深度优先遍历的规范递归实现将按最深级别的顺序消耗内存(在堆栈上)，在平衡树上它将是 log(n).
It depends what kind of traversal you are performing and the algorithm, but typically it would be O(n) where n is the total number of nodes in the tree. The canonical recursive implementation of depth first traversal, will consume memory (on the stack) in the order of the deepest level, which on a balanced tree it would be log(n).
这篇关于树遍历的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
